#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef long double ld;
typedef pair<int, int> P;

template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}

template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}

// Square Division
// divide [li, ri)

struct SquareDivision{
	int n, D;
	vector<int> l, r;
	SquareDivision(int n, int D = -1) : n(n), D(D) {}
	bool initialized = false;
	void init(){
		assert(n > 0);
		initialized = true;
		if(D == -1) D = sqrt(n);
		assert(D >= 1 and D <= n);
		l.resize(D);
		r.resize(D);
		l[0] = 0;
		int width = n / D;
		assert(width > 0);
		rep(i, D - 1){
			r[i] = l[i] + width;
			l[i + 1] = r[i];
		}
		r[D - 1] = n;
	}
	tuple<vector<int>, vector<int>, vector<int>> divide(int li, int ri){
		vector<int> minor_left;
		vector<int> major;
		vector<int> minor_right;
		int li_major = lower_bound(l.begin(), l.end(), li) - l.begin();
		int ri_major = lower_bound(r.begin(), r.end(), ri) - r.begin();
		if(li_major >= ri_major){
			for(int minor_idx = li; minor_idx < ri; minor_idx++) minor_left.push_back(minor_idx);
		}else{
			for(int minor_idx = li; minor_idx < l[li_major]; minor_idx++) minor_left.push_back(minor_idx);
			for(int major_idx = li_major; major_idx < ri_major; major_idx++) major.push_back(major_idx);
			for(int minor_idx = l[ri_major]; minor_idx < ri; minor_idx++) minor_right.push_back(minor_idx);
		}
		return make_tuple(minor_left, major, minor_right);
	}
};

// https://ei1333.github.io/luzhiled/snippets/math/mod-pow.html
template< typename T >
T mod_pow(T x, T n, const T &p) {
  T ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret;
}


int main(){
	int N, B, Q;
	cin >> N >> B >> Q;
	
	int D = max((int)sqrt((double)N / B), 1);
	SquareDivision sq(N, D);
	sq.init();
	
	vector<int> in(N + 1);
	vector<int> out(N + 1);
	int t = 0;
	
	auto dfs = [&](int from, auto dfs) -> void{
		if(from > N) return;
		in[from] = t; t++;
		dfs(from * 2, dfs);
		dfs(from * 2 + 1, dfs);
		out[from] = t;
	};
	dfs(1, dfs);
	
	vector<vector<int>> transfer(D, vector<int>(B));
	rep(i, D) rep(j, B) transfer[i][j] = j;
	
	vector<int> belong(N);
	rep(i, D){
		for(int x = sq.l[i]; x < sq.r[i]; x++) belong[x] = i;
	}
	
	vector<int> a(N);
	vector<vector<int>> cnt(D, vector<int>(B));
	vector<int> sum(D);
	
	for(int x = 1; x <= N; x++){
		int idx = in[x];
		int i = belong[idx];
		a[idx] = x % B;
		cnt[i][x % B]++;
		sum[i] += x % B;
	}
	
	auto change_minor = [&](int idx, int c){
		int i = belong[idx];
		
		cnt[i][a[idx]]--;
			
		a[idx] = c;
		
		cnt[i][a[idx]]++;
	};
	
	auto change_major = [&](int i, vector<int> transfer_sub){
		vector<int> cnt_sub(B);
		rep(j, B){
			sum[i] -= transfer[i][j] * cnt[i][j];
		}
		rep(j, B){
			transfer[i][j] = transfer[i][transfer_sub[j]];
		}
		rep(j, B){
			sum[i] += transfer[i][j] * cnt[i][j];
		}
	};
	
	auto evaluate = [&](int i){
		for(int idx = sq.l[i]; idx < sq.r[i]; idx++){
			change_minor(idx, transfer[i][a[idx]]);
		}
		rep(j, B) transfer[i][j] = j;
	};
	
	rep(_, Q){
		int x;
		long long d;
		cin >> x >> d;
		
		vector<int> transfer_sub(B);
		rep(j, B) transfer_sub[j] = (mod_pow<long long>(j, d, B) + 1) % B;
		
		auto [minor_left, major, minor_right] = sq.divide(in[x], out[x]);
		/*
		cout << "minor_left: " << minor_left;
		cout << "major: "  << major;
		cout << "minor_right: "  << minor_right;
		cout << "\n";
		*/
		
		int ans = 0;
		
		if(minor_left.size()){
			int i = belong[minor_left[0]];
			evaluate(i);
			
			for(int x : minor_left){
				change_minor(x, transfer_sub[a[x]]);
				ans += a[x];
			}
		}
		
		for(int i : major){
			change_major(i, transfer_sub);
			ans += sum[i];
		}
		
		if(minor_right.size()){
			int i = belong[minor_right[0]];
			evaluate(i);
			
			for(int x : minor_right){
				change_minor(x, transfer_sub[a[x]]);
				ans += a[x];
			}
		}
		cout << ans % B << "\n";
	}
	
	return 0;
}