【正经题解】列队

观察到 $q$ ≤ $500$ ，也就是说有效的行数不超过 $500$ 行。
我们把行数离散化。
那么需要维护的数的数量最多只有 $q$ ( $m$ ? $1$ ) $+n$ 个
发现有 $x_i$ $=1$ ，也就是说，有效的格子只有第一行和最后一列。
我们把第一行和最后一列压到一起去，那么我们要对这个序列支持：
删除第 $k$ 个元素
在末尾添加一个元素
这个操作能用平衡树实现，但是我用树状数组来实现。
用树状数组维护一个 $01$ 序列，第 $i$ 位上是 $0$ 表示这个位置上的数已经被删除了或者还没有被插入，第 $i$ 位上是 $1$ 表示这一位上的数没有被删除。
那么删除操作就是 $1$ → $0$ ，插入操作就是 $0$ → $1$ 。
第 $k$ 个元素就是前缀和为 $k$ 的位置。
对于查找这个位置的操作，我使用树状数组二分
定义一行中原来的元素为初始时这一行前 $m$ ? $1$ 个元素中，没有离队过的元素。
我们观察到对于本来就在这一行中的元素，我们可以直接算出它的值，而不用存储。
那么我们判断每一次询问是不是在本行的原来的元素中，如果是，直接判断掉。
那么每一行的“非原来的元素”有多少个呢？
我们不知道一行会有多少个，但是我们知道，所有行的这样的元素个数的总和不超过 $q$ 个。
这启发了我们对于每一行，只对其“非原来的元素”开一个树状数组维护。
而对于“原来的元素”，我们直接离线预处理。
预处理时需要对所有的询问按照 $x_i$ 为第一关键字，询问编号为第二关键字排序。
再对最后一列单独处理。

#pragma GCC optimize("O2")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;++i)
#define dF(i,a,b) for(int i=a;i>=b;--i)
#define F2(i,a,b) for(int i=a;i<b;++i)
#define getchar() (SS==TT&&(TT=(SS=BB)+fread(BB,1,1<<15,stdin),TT==SS)?EOF:*SS++)
#define RR register
char BB[1<<15],*SS=BB,*TT=BB;
inline int read(){
	RR int x;RR bool f;RR char c;
	for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
	for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
	return f?-x:x;
}
using namespace std;
int q,I[300010];
long long n,m,a[300010],b[300010];
inline bool cmp(int p1,int p2){return a[p1]==a[p2]?p1<p2:a[p1]<a[p2];}
int h[300010],len[300010],len2[300010],bit[900010];
long long arr[900010];
long long Ans[300010];
inline void Ins(int*array,int siz,int i,int x){for(;i<=siz;array[i]+=x,i+=i&-i);}
inline int binary(int*array,int siz,int x){
	int l=1,r,mid,sum,ans;
	while(l<=siz&&array[l]<x) l<<=1, ans=l;
	r=l; sum=array[l>>=1];
	while(l<r-1){
		mid=l+r>>1;
		if(mid>siz||array[mid]+sum>=x) r=mid, ans=mid;
		else l=mid, sum+=array[l];
	} ans=r;
	return ans;
}
int stk[300001],top;
int main(){
	n=read(), m=read(), q=read();
	F(i,1,q) a[i]=read(), b[i]=read(), I[i]=i;
	sort(I+1,I+q+1,cmp);
	F(i,1,m-1) Ins(bit,m-1,i,1);
	F(i,1,n) len[i]=m-1;
	F(i,1,q){
		if(a[I[i-1]]!=a[I[i]])
			while(top) Ins(bit,m-1,stk[top--],1);
		if(b[I[i]]>len[a[I[i]]]) continue;
		int pos=binary(bit,m-1,b[I[i]]);
		Ans[I[i]]=(a[I[i]]-1)*m+pos;
		Ins(bit,m-1,pos,-1);
		stk[++top]=pos;
		--len[a[I[i]]];
	}
	int iter=0;
	F(i,1,n){
		while(iter<=q&&a[I[iter]]<i) ++iter;
		h[i]=iter-1;
	}
	h[n+1]=q;
	memset(bit,0,sizeof bit);
	F(i,1,n) len[i]=0, len2[i]=m-1; len[n+1]=n;
	F(i,1,n) Ins(bit+h[n+1],n+q,i,1), arr[q+i]=i*m;
	F(i,1,q){
		if(Ans[i]){
			int pos=binary(bit+h[n+1],n+q,a[i]);
			Ins(bit+h[n+1],n+q,pos,-1);
			Ins(bit+h[n+1],n+q,++len[n+1],1);
			arr[h[n+1]+len[n+1]]=Ans[i];
			Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],++len[a[i]],1);
			arr[h[a[i]]+len[a[i]]]=arr[h[n+1]+pos];
			--len2[a[i]];
		}
		else{
			int pos=binary(bit+h[n+1],n+q,a[i]);
			Ins(bit+h[n+1],n+q,pos,-1);
			Ins(bit+h[n+1],n+q,++len[n+1],1);
			if(b[i]!=m){
				int pos2=binary(bit+h[a[i]],h[a[i]+1]-h[a[i]],b[i]-len2[a[i]]);
				Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],pos2,-1);
				Ans[i]=arr[h[a[i]]+pos2];
				Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],++len[a[i]],1);
				arr[h[a[i]]+len[a[i]]]=arr[h[n+1]+pos];
			} else Ans[i]=arr[h[n+1]+pos];
			arr[h[n+1]+len[n+1]]=Ans[i];
		}
	}
	F(i,1,q) printf("%lld\n",Ans[i]);
	return 0;
}