#include<stdio.h>
long long int seg[2][1000006], ss;
void update(long long int z, long long int x, long long int d)
{
	x += ss - 1;
	seg[z][x] += d;
	while (x > 0)
	{
		x = (x - 1) / 2;
		seg[z][x] = seg[z][2 * x + 1] + seg[z][2 * x + 2];
	}
	return;
}
long long int get(long long int z, long long int l, long long int r)
{
	l += ss - 1;
	r += ss - 1;
	long long int res = 0;
	while (l < r)
	{
		if (l % 2 == 0)
			res += seg[z][l];
		l /= 2;
		if (r % 2 > 0)
			res += seg[z][r];
		r = r / 2 - 1;
	}
	if (l == r)
		res += seg[z][l];
	return res;
}
long long int L[1000006];
long long int a[1000006];
int main()
{
	long long int n, q;
	scanf("%lld %lld %lld", &n, &q, &L[0]);
	long long int i;
	for (i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	for (ss = 1; ss < 200005; ss *= 2);
	for (i = 0; i < 2 * ss - 1; i++)
		seg[0][i] = seg[1][i] = 0;
	for (i = 0; i < n; i++)
	{
		update(0, a[i], 1);
		update(1, a[i], a[i]);
	}
	long long int t, l, r, cnt = 0;
	for (i = 1; i <= q; i++)
	{
		L[i] = L[i - 1];
		scanf("%lld", &t);
		if (t == 1)
		{
			scanf("%lld", &l);
			update(0, l, 1);
			update(1, l, l);
		}
		else if (t == 2)
		{
			scanf("%lld %lld", &l, &r);
			printf("%lld %lld\n", get(0, l, r), get(1, l, r));
			cnt++;
		}
		else
		{
			scanf("%lld", &l);
			L[i] = l;
		}
	}
	if (cnt == 0)
		printf("Not Found!\n");
	return 0;
}