#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 8e5+10;
const int mod = 998244353;

ll bpow(ll x, ll y)
{
	ll ans = 1;
	while(y > 0)
	{
		if(y & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

struct idfer
{
	ll cont; // content
	bool ogarr; // 0 -> arr, 1 -> queries
	int ogidx;
	int validx;
	inline bool operator<(const idfer &other) const
	{
		return cont < other.cont;
	}
};

int n, k, w, q;

ll fac[maxn];
ll rev[maxn];

int len[maxn];
ll anmod[maxn][5];
ll ansum[maxn][5];

ll arr[maxn];
pii queries[maxn];
idfer nqris[maxn];
idfer vals[maxn];
idfer narr[maxn];

ll ncr(ll n, ll r)
{
	return fac[n] * rev[r] % mod * rev[n-r] % mod;
}

void upd(int v)
{
	len[v] = len[2*v] + len[2*v+1];
	int sz = len[2*v];
	for(int i = 0; i < w; i++)
		anmod[v][i] = (anmod[2*v][i] + anmod[2*v+1][(i+sz)%w]) % mod;
	for(int i = 0; i <= k; i++)
		ansum[v][i] = ansum[2*v][i];
	ansum[v][0] += ansum[2*v+1][0];
	for(int i = 1; i <= k; i++)
	{
		for(int j = 0; j <= i; j++)
			ansum[v][i] += ansum[2*v+1][j] * bpow(sz, i-j) % mod * ncr(i, j) % mod;
	}
}

void debug_ansum(int l, int r, int v)
{
	cerr << "ansum[" << l << "~" << r << "," << v << "]: ";
	for(int i = 0; i <= k; i++)
		cerr << ansum[v][i] << " ";
	cerr << endl;
}

void set_state(int l, int r, int p, bool st, int v)
{
	if(p < l or p >= r)
		return;
	if(r - l == 1)
	{
		len[v] = st;
		for(int i = 0; i < w; i++)
			anmod[v][i] = st * vals[p].cont % w * bpow(i, k) % w;
		for(int i = 0; i <= k; i++)
			ansum[v][i] = st * vals[p].cont % mod * bpow(1, k) % mod;
		return;
	}
	int m = (l+r) / 2;
	set_state(l, m, p, st, 2*v);
	set_state(m, r, p, st, 2*v+1);
	upd(v);
}

ll get()
{
	ll ans = (ansum[1][k] - anmod[1][1] + mod) % mod;
	ans = ans * rev[w] % mod;
	return ans;
}

void debug_vals() 
{
	cerr << "----vals----" << endl;
	for(int i = 0; i < n+q; i++)
		cerr << vals[i].cont << " " << vals[i].validx << " " << vals[i].ogarr << " " << vals[i].ogidx << endl;
	cerr << "--endvals--" << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	fac[0] = 1;
	for(int i = 1; i < maxn; i++)
		fac[i] = fac[i-1] * i % mod;
	rev[maxn-1] = bpow(fac[maxn-1], mod-2);
	for(int i = maxn-2; i >= 0; i--)
		rev[i] = rev[i+1] * (i+1) % mod;
	cin >> n >> k >> w;
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	cin >> q;
	for(int i = 0; i < q; i++)
	{
		cin >> queries[i].first >> queries[i].second;
		queries[i].first--;
	}
	int nlen = n+q;
	for(int i = 0; i < n; i++)
		vals[i] = {arr[i], 0, i, -1};
	for(int i = 0; i < q; i++)
		vals[i+n] = {queries[i].second, 1, i, -1};
	sort(vals, vals+nlen);
	for(int i = 0; i < nlen; i++)
	{
		vals[i].validx = i;
		if(vals[i].ogarr == 0)
		{
			narr[vals[i].ogidx] = vals[i];
			set_state(0, nlen, i, 1, 1);
		}
		else
		{
			nqris[vals[i].ogidx] = vals[i];
		}
	}
	for(int i = 0; i < q; i++)
	{
		int idx = queries[i].first;
		idfer f = narr[idx];
		idfer s = nqris[i];
		set_state(0, nlen, f.validx, 0, 1);
		set_state(0, nlen, s.validx, 1, 1);
		cout << get() << endl;
	}
	return 0;
}