RT, WA on #9

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof a)
#define pii pair<ll, ll>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
const ll N = 2e5 + 15, M = 2e6;
const ll mod = 1e9 + 7, mod2 = 998244353;
const ld eps = 1e-6;

ll n, q, m;

ll block, Len;

ll belong[N], L[N], R[N], Sum[N], mul[N], add[N];

ll Arr[N];

void build()
{
	Len = n / block; 
	if (n % block) ++ Len;
	for (ll i = 1; i <= Len; i ++ ) 
	{
		mul[i] = 1, add[i] = 0;
		L[i] = (i - 1) * block + 1, R[i] = i * block;
	}
	for (ll i = 1; i <= n; i ++ ) belong[i] = (i - 1) / block + 1;
	for (ll i = 1; i <= n; i ++ ) Sum[belong[i]] += Arr[i] % m; 
}

void mult(ll l, ll r, ll k)
{
	ll bl = belong[l], br = belong[r];
	if (bl == br)
	{
		if (add[bl] || mul[bl] != 1)
		{
			for (ll i = L[bl]; i <= R[bl]; i ++ )
			{
				Arr[i] = (Arr[i] * mul[bl] % m + add[bl]) % m;	
			} 
			Sum[bl] = (Sum[bl] * mul[bl] % m + add[bl] * block) % m;
			add[bl] = 0, mul[bl] = 1;
		}
		ll More = 0;
		for (ll i = l; i <= r; i ++ )
		{
			More = (More + Arr[i] * (k - 1)) % m, Arr[i] = (Arr[i] * k) % m;
		}
		Sum[bl] = (Sum[bl] + More) % m;
		return ;
	}
	if (add[bl] || mul[bl] != 1)
	{
		for (ll i = L[bl]; i <= R[bl]; i ++ ) 
		{
			Arr[i] = (Arr[i] * mul[bl] % m + add[bl]) % m;
		}
		Sum[bl] = (Sum[bl] * mul[bl] % m + add[bl] * block) % m;
		add[bl] = 0, mul[bl] = 1;
	}
	ll More = 0;
	for (ll i = l; i <= R[bl]; i ++ ) More = (More + Arr[i] *  (k - 1)) % m, Arr[i] = (Arr[i] * k) % m;
	Sum[bl] = (Sum[bl] + More) % m;
	
	if (add[br] || mul[br] != 1)
	{
		for (ll i = L[br]; i <= R[br]; i ++ ) 
		{
			Arr[i] = (Arr[i] * mul[br] % m + add[br]) % m;
		}
		Sum[br] = (Sum[br] * mul[br] % m + add[br] * block) % m;
		add[br] = 0, mul[br] = 1;
	}
	More = 0;
	for (ll i = L[br]; i <= r; i ++ ) More = (More + Arr[i] * (k - 1)) % m, Arr[i] = (Arr[i] * k) % m;
	Sum[br] = (Sum[br] + More) % m;
	
	for (ll i = bl + 1; i < br; i ++ )
	{
		mul[i] = (mul[i] * k) % m;
		add[i] = (add[i] * k) % m;
	}
}

void adds(ll l, ll r, ll k)
{
	ll bl = belong[l], br = belong[r];
	if (bl == br)
	{
		if (add[bl] || mul[bl] != 1)
		{
			for (ll i = L[bl]; i <= R[bl]; i ++ )
			{
				Arr[i] = (Arr[i] * mul[bl] + add[bl]) % m;	
			} 
			Sum[bl] = (Sum[bl] * mul[bl] + add[bl] * block) % m;
			add[bl] = 0, mul[bl] = 1;
		}
		for (ll i = l; i <= r; i ++ ) Arr[i] = (Arr[i] + k) % m;
		Sum[bl] = (Sum[bl] + (r - l + 1) * k) % m;
		return ;
	}
	if (add[bl] || mul[bl] != 1)
	{
		for (ll i = L[bl]; i <= R[bl]; i ++ )
		{
			Arr[i] = (Arr[i] * mul[bl] % m + add[bl]) % m;	
		} 
		Sum[bl] = (Sum[bl] * mul[bl] + add[bl] * block) % m;
		add[bl] = 0, mul[bl] = 1;
	}
	for (ll i = l; i <= R[bl]; i ++ ) Arr[i] = (Arr[i] + k) % m;
	Sum[bl] = (Sum[bl] + (R[bl] - l + 1) * k) % m; 
	
	if (add[br] || mul[br] != 1)
	{
		for (ll i = L[br]; i <= R[br]; i ++ )
		{
			Arr[i] = (Arr[i] * mul[br] + add[br]) % m;	
		} 
		Sum[br] = (Sum[br] * mul[br] % m + add[br] * block) % m;
		add[br] = 0, mul[br] = 1;
	}
	for (ll i = L[br]; i <= r; i ++ ) Arr[i] += k, Arr[i] %= m;
	Sum[br] = (Sum[br] + (r - L[br] + 1) * k) % m; 
	for (ll i = bl + 1; i < br; i ++ ) add[i] = (add[i] + k) % m;
}

ll Q(ll l, ll r)
{
	ll bl = belong[l], br = belong[r], ans = 0;
	if (bl == br)
	{
		for (ll i = l; i <= r; i ++ ) ans = (ans + Arr[i]) % m;
		ans = ans * mul[bl] % m + (r - l + 1) * add[bl] % m; ans %= m;
		return ans;
	}
	for (ll i = l; i <= R[bl]; i ++ ) ans = (ans + Arr[i]) % m;
	ans = ans * mul[bl] % m + (R[bl] - l + 1) * add[bl] % m; ans %= m;
	
	ll T = ans; ans = 0;
	
	for (ll i = L[br]; i <= r; i ++ ) ans = (ans + Arr[i]) % m;
	ans = ans * mul[br] % m + (r - L[br] + 1) * add[br] % m; ans %= m;
	ans += T; ans %= m;
	
	for (ll i = bl + 1; i < br; i ++ )
	{
		ans = (ans + Sum[i] * mul[i] % m + add[i] * block) % m;
	}
	return ans % m;
}

signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	FstIO; 

	cin >> n >> m; block = sqrt(n);
	for (ll i = 1; i <= n; i ++ ) cin >> Arr[i];
	cin >> q;
	build();
	while (q -- )
	{
		ll opt; cin >> opt;
		if (opt == 1)
		{
			ll x, y, k; cin >> x >> y >> k;
			mult(x, y, k);
		}
		else if (opt == 2)
		{
			ll x, y, k; cin >> x >> y >> k;
			adds(x, y, k);
		}
		else if (opt == 3)
		{
			ll x, y; cin >> x >> y;
			cout << Q(x, y) << '\n';
		}
	}
}