#include "Alice.h"
#include<bits/stdc++.h>
using namespace std;typedef long long ll;typedef pair<int,int> pii;
const int n=5000;const ll inf=1e18;ll k;vector<pii>ans;
vector<pii>Alice(){k=setN(n);for(int i=1;i<n;++i)ans.push_back(make_pair(k%i+1,i+1));return ans;}

/*
signed main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i]=read(),b[i]=read();
	ans=b[1],M=a[1];
	for(int i=2;i<=n;++i)
B=((b[i]-ans)%a[i]+a[i])%a[i],g=exgcd(M,a[i],x,y),x=mul(x,B/g,a[i]);
ans+=M*x,M*=a[i]/g,(ans+=M)%=M;
	write(ans);
*/
#include "Bob.h"
#include<bits/stdc++.h>
using namespace std;typedef long long ll;typedef __int128 lll;typedef pair<int,int> pii;lll exgcd(lll a,lll b,lll&x,lll&y)
{if(!b)return x=1,y=0,a;lll ans=exgcd(b,a%b,x,y);lll tmp=x;x=y,y=tmp-a/b*y;return ans;}
const int n=5000;const lll inf=1e18,I=1;lll k,x,y,xx,yy,g,z;vector<pii>ans;lll mul(lll x,lll y,lll m){lll ans=0;while(y){if(y&I)ans=(ans+x)%m;y>>=I,x=(x<<I)%m;}return ans;}
ll Bob(vector<pii>V){lll a=0,b=0;/*srand(time(0)),random_shuffle(V.begin(),V.end());*/for(auto i:V){x=i.second-1,y=i.first-1;if(!a)a=x,b=y;else{g=exgcd(a,x,xx,yy);
/*if(a/g*x>8*inf)continue;*/xx=mul(((y-b%x+x)%x)/g,xx,x),a*=x/g,b=(b+mul(a/(x/g),xx,a))%a;if(a>inf)break;}}return (ll)b;}