样例能过，交上去全Wa

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i ++)
using namespace std;

const int N = 200009;
typedef unsigned int LL;

int n, m, q, bk, pid[N], pos[N << 1], now[N << 1];
struct dd {
	int op, x, y, id;
} e[N], g[N];
LL ans[N], cur, t[N << 1], a[N << 1];

inline int read() {
	int x = 0; char c = getchar(); while(! isdigit(c)) c = getchar();
	while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x;
}

inline bool ssd(dd x, dd y) {
	return (pid[x.y] == pid[y.y] ? ((pid[x.y] & 1) ? x.x < y.x : x.x > y.x) : x.y < y.y);
}

// now[x] -> 原序列中x现在的位置
// pos[x] -> 现在x位置上现在对应原序列的位置
// t[x] -> 现在的x位置被询问几次 
// a[x] -> 现在x位置上的权值
 

inline void addr(int r)
{
	int op = e[r].op, x = e[r].x, y = e[r].y;
	if(op ^ 3) swap(a[x], a[y]), swap(pos[x], pos[y]), swap(t[x], t[y]), swap(now[pos[x]], now[pos[y]]);
	else cur += a[x], t[x] ++;
}

inline void addl(int l)
{
	int op = e[l].op, x = e[l].x, y = e[l].y;
	if(op ^ 3)
	{
		swap(a[now[x]], a[now[y]]), swap(pos[now[x]], pos[now[x]]), swap(now[x], now[y]);
		cur += (t[now[x]] - t[now[y]]) * (a[now[x]] - a[now[y]]);
	}
	else cur += a[now[x]], t[now[x]] ++;
}

inline void delr(int r)
{
	int op = e[r].op, x = e[r].x, y = e[r].y;
	if(op ^ 3) swap(a[x], a[y]), swap(pos[x], pos[y]), swap(t[x], t[y]), swap(now[pos[x]], now[pos[y]]);
	else cur -= a[x], t[x] --;
}

inline void dell(int l)
{
	int op = e[l].op, x = e[l].x, y = e[l].y;
	if(op ^ 3)
	{
		cur -= t[now[x]] * (a[now[x]] - a[now[y]]);
		cur -= t[now[y]] * (a[now[y]] - a[now[x]]);
		swap(now[x], now[y]), swap(pos[now[x]], pos[now[x]]), swap(a[now[x]], a[now[y]]);
	}
	else cur -= a[now[x]], t[now[x]] --;
}

int main()
{
//	freopen("auto.in", "r", stdin);
//	freopen("auto.out", "w", stdout);
	n = read(), m = read();
	rep(i, 1, n) a[i] = read();
	rep(i, 1, m)
	{
		e[i].op = read(), e[i].x = read();
		if(e[i].op ^ 3) e[i].y = read();
		if(e[i].op == 1) a[++ n] = e[i].y, e[i].y = n;
	}
	q = read(); bk = ceil(m * 1.0 / sqrt(q * 1.0));
	rep(i, 1, q) g[i].y = read(), g[i].x = read(), g[i].id = i;
	rep(i, 1, m) pid[i] = (i - 1) / bk + 1;
	sort(g + 1, g + q + 1, ssd);
	rep(i, 1, n) now[i] = pos[i] = i;
	int l = 1, r = 0;
	rep(i, 1, q)
	{
		int L = g[i].y, R = g[i].x;
		while(r < R) addr(++ r);
		while(l > L) addl(-- l);
		while(r > R) delr(r --);
		while(l < L) dell(l ++);
		ans[g[i].id] = cur;
	}
	rep(i, 1, q) printf("%u\n", ans[i]);
	return 0;
}