如题

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define stop getchar();getchar();
#define ll long long

const int maxn = 5 * 1000010;
int n,m,q;

#define in inline 
#define re register 

in int read(){
	int x = 0;
	char ch = 'a';
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') {
	    x = (x << 1) + (x << 3) + ch - '0';
		ch = getchar();
	}
	return x;
}

struct poi{
	int ch[2],f;
	ll size,cnt,l,r;
};
struct ccy{
    poi s[maxn];
    int tot,root;
    in void update(int x){
    	if(x == 0) return ;
    	s[x].size = s[x].r - s[x].l + (ll)1;
    	s[x].cnt = s[x].size;
    	if(s[x].ch[0]) s[x].size += (ll)s[s[x].ch[0]].size;
    	if(s[x].ch[1]) s[x].size += (ll)s[s[x].ch[1]].size;
		return ;
	}
    in void rotate(int x){
	    int f = s[x].f,fa = s[f].f;
	    if(f == 0){
	    	root = x;
	    	return ;
		}
    	bool w = (x == s[f].ch[1]);
    	s[f].ch[w] = s[x].ch[w ^ 1];
    	s[f].f = x;
    	if(s[x].ch[w ^ 1]) s[s[x].ch[w ^ 1]].f = f;
    	s[x].ch[w ^ 1] = f;
		s[x].f = fa;
    	if(fa) s[fa].ch[s[fa].ch[1] == f] = x;
		update(f);
		update(x);
		return ;
	}
	in void splay(int x){
		int fa = s[x].f;
		int gf = s[fa].f;
		while(fa){
			if(gf){
				if((fa == s[gf].ch[1]) == (x == s[fa].ch[1])) rotate(fa);
			    else rotate(x);
			}
			rotate(x);
			fa = s[x].f;
			gf = s[fa].f;
		}
		root = x;
		return ;
	}
	in void insert(ll l,ll r,ll pl){
		//pl是排在当前节点前面的节点总大小 
		int now = root,lst = 0;
		ll num = pl;
		bool w = 0;
		while(1){
			if(now == 0){ 
				s[++tot].l = l;
				s[tot].r = r;
				s[tot].f = lst;
				update(tot);
				if(lst != 0) {
					s[lst].ch[w] = tot;
					update(lst);
				}
				splay(tot);
				return ;
			}
			if(s[now].cnt + s[s[now].ch[0]].size <= num){
				num -= s[now].cnt + s[s[now].ch[0]].size;
				lst = now;
				w = 1;
				now = s[now].ch[1];
			}
			else lst = now,now = s[now].ch[0],w = 0;
		}
		return ;
	}
    in int find(ll x){
    	int now = root;
		ll num = x;
    	while(1){
    		if(num <= s[s[now].ch[0]].size) now = s[now].ch[0];
    		else if(num <= s[s[now].ch[0]].size + s[now].cnt)  return now;
    		else {
    			num -= s[s[now].ch[0]].size + s[now].cnt;
    			now = s[now].ch[1];
			}
		}
	}
	in ll fin(ll x){
		int now = root;
		ll num = x;
    	while(1){
    		if(num <= s[s[now].ch[0]].size) now = s[now].ch[0];
    		else if(num <= s[s[now].ch[0]].size + s[now].cnt) {
    			return num - s[s[now].ch[0]].size;
			}
    		else {
    			num -= s[s[now].ch[0]].size + s[now].cnt;
    			now = s[now].ch[1];
			}
		}
	}
	in int pre(){
		int now = s[root].ch[0];
		while(s[now].ch[1]) now = s[now].ch[1];
		return now; 
	}
	in int nex(){
		int now = s[root].ch[1];
		while(s[now].ch[0]) now = s[now].ch[0];
		return now;
	}
	in void del(int x){
		update(x);
		splay(x);
		if(!s[root].ch[0] && !s[root].ch[1]) {
			root = 0;
			return ;
		}
		for(int k = 0;k <= 1; k++){
			if(!s[root].ch[k]){
				root = s[root].ch[k ^ 1];
				s[root].f = 0;
				return ;
			}
		}
		int now = root;
		splay(pre());
		s[root].ch[1] = s[now].ch[1];
		s[s[now].ch[1]].f = root;
		update(s[root].ch[1]);
		update(root);
		return ;
	}
	in void workq(int x){
    	int t = find(x);
    	ll l = s[t].l,r = s[t].r;
		printf("%lld\n",l);
		//if(l == 874480) cout<<"ww"<<endl;
		del(t);
    	insert(l,r,m - 1);
    	return ;
	}
	void print(int x){
		for(int i = 1;i <= x; i++) cout<<s[find(i)].l<<" ";
		cout<<endl;
		cout<<endl;
	}
};

ccy sq,qu;
//方阵，队列 

int numm = 1;

in void works(ll x,ll y){
		int t = sq.find((x - 1) * (m - 1) + y);
		ll li = sq.fin((x - 1) * (m - 1) + y);
		ll L = sq.s[t].l,R = sq.s[t].r;
		printf("%lld\n",L + li - 1);
		if(sq.s[t].cnt == 1) {
			sq.del(t);
			int tt = qu.find(x);
			sq.insert(qu.s[tt].l,qu.s[tt].r,(x - 1) * (m - 1) + m - 2);
			qu.del(tt);
			qu.insert(L,L,n - 1);	
		}
		else {
			if(li == 1){
				sq.s[t].l++;
				sq.update(t);
				sq.splay(t);
			}
			else if(li + L - 1 == R){
				sq.s[t].r--;
				sq.update(t);
				sq.splay(t);
			}
			else {
				sq.s[t].r = sq.s[t].l + li - 2;
			    sq.update(t);
			    sq.splay(t);
			    int tt = sq.nex();
			    bool w = 0;
			    if(tt == 0) tt = t,w = 1;
			    sq.s[tt].ch[w] = ++sq.tot;
			    sq.s[sq.tot].l = sq.s[t].r + 2;
			    sq.s[sq.tot].r = R;
			    sq.s[sq.tot].f = tt;
			    sq.update(sq.tot);
			    sq.splay(sq.tot);
			}
			int tt = qu.find(x);
			//if(qu.s[tt].l == 874480) cout<<x<<endl;
			sq.insert(qu.s[tt].l,qu.s[tt].r,(x - 1) * (m - 1) + m - 2);
			qu.del(tt);
			qu.insert(L + li - 1,L + li - 1,n - 1);
		}
		
		return ;
	}

int main(){
	freopen("1.txt","r",stdin);
	//freopen("121212.txt","w",stdout);
	freopen("2.txt","w",stdout);
	sq.root = 0;
	qu.root = 0;
	n = read();
	m = read();
	q = read();
	for(re int i = 1;i <= n; i++){
		sq.insert((ll)(i - 1) * m + 1,(ll)i * m - 1,(ll)(i - 1) * (m - 1));
	}
	for(re int i = 1;i <= n; i++){
		qu.insert((ll)i * m,(ll)i * m,(ll)i - 1);
	}
	for(re int i = 1;i <= q; i++){
		int x = read(),y = read();
		if(y == m) qu.workq(x);
		else {works(x,y);}	
	}
	return 0;
}