#include using namespace std; typedef signed long long ll; #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define FORR2(x,y,arr) for(auto& [x,y]:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) template bool chmax(T &a, const T &b) { if(a bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;} //------------------------------------------------------- ll L; int N,Q; ll A[1<<19]; ll X[1<<19]; ll D; struct node { ll dif; ll ma,mi,up,down; }; node merge(node a,node b) { node v; if(a.ma==0&&a.mi==0) return b; if(b.ma==0&&b.mi==0) return a; v.dif=a.dif+b.dif; v.ma=max(a.ma,a.dif+b.ma); v.mi=min(a.mi,a.dif+b.mi); v.up=max({a.up,b.up,b.ma+a.dif-a.mi}); v.down=min({a.down,b.down,b.mi+a.dif-a.ma}); return v; } node def; template class SegTree_1 { public: vector val; SegTree_1(){val=vector(NV*2,def);}; V getval(ll x,ll y,int l=0,int r=NV,int k=1) { // x<=i st; void solve() { int i,j,k,l,r,x,y; string s; cin>>L>>N>>Q; A[0]=0; FOR(i,N) { cin>>A[i+1]; } for(i=N+1;i<1<<18+1;i++) A[i]=1LL<<53; for(i=1;i<1<<18;i++) { if(i%2==1) X[i]=X[i-1]+A[i]-A[i-1]; else X[i]=X[i-1]-(A[i]-A[i-1]); } N+=2; FOR(i,N-1) { node& v=st.val[i+(1<<18)]; v.dif=X[i+1]-X[i]; if(X[i+1]>X[i]) { v.dif=v.ma=v.up=X[i+1]-X[i]; v.mi=v.down=0; } else { v.dif=v.mi=v.down=X[i+1]-X[i]; v.ma=v.up=0; } } for(i=(1<<18)-1;i>=1;i--) st.val[i]=merge(st.val[i*2],st.val[i*2+1]); while(Q--) { ll B,C; cin>>B>>C; B=(B+D)%L; C=(C+D)%1000000000000000LL; D=((1LL<<52)-1); for(i=51;i>=0;i--) { ll t=D-(1LL<=B||v.down<=B-L) D=t; } cout<