#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>


typedef long long ll;
typedef long double ld;

using namespace std;
const int MAXN = 620000;

char buf[100];
int t, n, m, q;

struct node {
	node *l, *r;
	ll sum, d;
	int c;
	node() {
		l = r = 0;
		sum = d = c = 0;
	}
};

node *rt[MAXN];
int a[MAXN];

node *newn() {
	return new node();
}

void push(node *v, int tl, int tr) {
	if (!v->c && !v->d)
		return;
	node *vl = newn();
	node *vr = newn();
	*vl = *(v->l);
	*vr = *(v->r);
	if (v->c) {
		vl->sum = 0;
		vl->d = 0;
		vl->c = 1;
		vr->sum = 0;
		vr->d = 0;
		vr->c = 1;
		v->c = 0;
	}
	int m = (tl + tr) >> 1;
	if (v->d) {
		vl->sum += v->d * (m - tl);
		vr->sum += v->d * (tr - m);
		vl->d += v->d;
		vr->d += v->d;
		v->d = 0;
	}
	v->l = vl;
	v->r = vr;
}

void upd(node *v) {
	v->sum = v->l->sum + v->r->sum;
}


node *build(int tl, int tr) {
	if (tl + 1 == tr)
		return newn();
	int m = (tl + tr) >> 1;
	node *nn = newn();
	nn->l = build(tl, m);
	nn->r = build(m, tr);
	return nn;
}

node *add(node *v, int tl, int tr, int l, int r) {
	if (tr <= l || r <= tl)
		return v;
	if (l <= tl && tr <= r) {
		node *v2 = newn();
		*v2 = *v;
		v2->sum += (tr - tl);
		v2->d++;
		return v2;
	}
	int m = (tl + tr) >> 1;
	node *v2 = newn();
	*v2 = *v;
	push(v2, tl, tr);
	v2->l = add(v2->l, tl, m, l, r);
	v2->r = add(v2->r, m, tr, l, r);
	upd(v2);
	return v2;
}

ll get(node *v, int tl, int tr, int l, int r) {
	if (tr <= l || r <= tl)
		return 0;
	if (l <= tl && tr <= r)
		return v->sum;
	int m = (tl + tr) >> 1;
	if (v->c)
		return (min(r, tr) - max(l, tl)) * v->d;
	return get(v->l, tl, m, l, r) + get(v->r, m, tr, l, r) + (min(r, tr) - max(l, tl)) * v->d;
}

node *del(node *v, int tl, int tr, int l, int r) {
	if (tr <= l || r <= tl)
		return v;
	if (l <= tl && tr <= r) {
		node *v2 = newn();
		*v2 = *v;
		v2->sum = 0;
		v2->c = 1;
		v2->d = 0;
		return v2;
	}
	int m = (tl + tr) >> 1;
	node *v2 = newn();
	*v2 = *v;
	push(v2, tl, tr);
	v2->l = del(v2->l, tl, m, l, r);
	v2->r = del(v2->r, m, tr, l, r);
	upd(v2);
	return v2;
}

void solvelr() {
	rt[n] = build(0, m);
	node *now = rt[n];
	for (int i = n - 1; i >= 0; --i) {
		now = add(now, 0, m, a[i], m);
		now = del(now, 0, m, 0, a[i]);
		rt[i] = now;
	}
	printf("%lld ", get(now, 0, m, 0, m));
	int mx = 0;
	ll sum = 0;
	for (int i = 0; i < q; ++i) {
		int pos, b;
		scanf("%d%d", &pos, &b);
		mx = max(mx, b);
		sum += m - mx;
		printf("%lld ", sum + get(rt[i + 1], 0, m, mx, m));
	}
	printf("\n");
}

ll sm[MAXN];
int mxx[MAXN];

void solverl() {
	int mx = 0;
	ll sum = 0;
	sm[0] = 0;
	mxx[0] = 0;
	for (int i = 0; i < n; ++i) {
		mx = max(mx, a[i]);
		sum += m - mx;
		sm[i + 1] = sum;
		mxx[i + 1] = mx;
	}
	printf("%lld ", sm[n]);
	node *now = build(0, m);
	for (int i = q - 1; i >= 0; --i) {
		int pos, b;
		scanf("%d%d", &pos, &b);
		now = add(now, 0, m, b, m);
		now = del(now, 0, m, 0, b);
		printf("%lld ", sm[i] + get(now, 0, m, mxx[i], m));
	}
	printf("\n");
}

int main() {
	scanf("%d%d%d", &t, &n, &m);
	for (int i = 0; i < n; ++i)
		scanf("%d", a + i);
    scanf("%d", &q);
	if (m == 0) {
		for (int i = 0; i <= q; ++i)
			printf("0 ");
		printf("\n");
		return 0;
	}
	if (t == 4 || t == 2 || t == 0)
		solvelr();
	else
		solverl();
	return 0;
}


