#include <bits/stdc++.h>
using namespace std;

long long qpow(int base, int p, int mod)  // base^p%mod
{
	long long ans = 1, tmp = base;
	while (p != 0)
	{
		if (p & 1) ans = (ans % mod * tmp % mod) % mod;
		tmp = (tmp % mod * tmp % mod) % mod;
		p	= p >> 1;
	}
	ans = ans % mod;
	return ans;
}

long long mpow(int b, int p, int mod)
{
	long long tmp = 1;
	for (int i = 1; i <= p; i++) tmp *= b, tmp %= mod;
	return tmp;
}

set<int> Tset;
int s[20051131];

int main()
{
	int n, q, k, i, v, ans;
	cin >> n >> q >> k;
	Tset.insert(n);
	s[n] = 1;
	ans	 = mpow(n, k, 20051131);
	for (int i = 1; i <= q; i++)
	{
		cin >> i >> v;
		auto t = Tset.lower_bound(i);
		int t0 = *t, s0 = s[t0];
		// cout << s0 << " " << t0 << endl;
		s[t0]	 = i;
		s[i - 1] = s0;
		// cout << t0 << " " << i << " " << i << " " << s0 << endl;
		Tset.insert(i - 1);
		ans -= mpow(t0 - s0 + 1, k, 20051131);
		ans += mpow(t0 - i + 1, k, 20051131);
		ans += mpow(i - s0, k, 20051131);
		cout << ans % 20051131 << endl;
	}
	return 0;
}

为啥0分啊？