//APIO 2024 Magic Show - Alice
//https://qoj.ac/contest/1684/problem/8726
#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
using ll = long long;
using vll = vector<ll>;
vector<pair<int,int>> Alice(){
ll n=5000, x=setN(n); vector<pair<int,int>> ans;
for(int i=1; i<n; i++){
if(x%i==0) ans.push_back({i,n});
else ans.push_back({i,x%i});
}
return ans;
}
//APIO 2024 Magic Show - Bob
//https://qoj.ac/contest/1684/problem/8726
#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
using ll = long long;
using i128 = __int128_t;
using vll = vector<ll>;
i128 gcd(i128 a,i128 b,i128 &x,i128 &y){
if(a==0){x=0; y=1; return b;}
i128 x1, y1, res=gcd(b%a,a,x1,y1);
x=y1-(b/a)*x1; y=x1; return res;
}
ll Bob(vector<pair<int,int>> g){
ll n=5000, a, b; i128 ans=0, mod=1;
for(auto [v,u]:g){
if(v>u) swap(v,u);
if(u==n) a=0, b=v;
else a=v, b=u;
i128 x, y, g=gcd(mod,i128(b),x,y), nMod=(mod/g)*b, temp=b/g;
i128 k=(x%temp+temp)%temp; k=(k*((((a-ans)%b+b)%b)/g))%temp;
ans=(ans+mod*k)%nMod; mod=nMod;
if(mod>(ll)1e18) break;
}
return (ll)ans;
}
