#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()
const int NM = 500;
const ll LIM = 1e18;
vector <int> arr_Alice[NM+5];
bool chk_Alice = 0;
mt19937 rng_Alice(69420);
vector <pii> Alice(){
ll X = setN(NM);
if (!chk_Alice){
for (int i = 2; i <= NM; i++){
arr_Alice[i].clear();
for (int j = 0; j < i-1; j++) arr_Alice[i].push_back(j+1);
shuffle(arr_Alice[i].begin(), arr_Alice[i].end(), rng_Alice);
}
chk_Alice = 1;
}
vector <pii> res = {};
for (int i = 2; i <= NM; i++){
res.push_back(mp(arr_Alice[i][X%(i-1)], i));
}
sort(res.begin(), res.end());
return res;
}
#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define pii pair <int, int>
#define pll pair <ll, ll>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()
const int NM = 500;
const ll LIM = 1e18;
vector <int> arr_Bob[NM+5];
bool chk_Bob = 0;
vector <pii> info;
int K, r[NM+5], m[NM+5], f[NM+5], cur[NM+5];
mt19937 rng_Bob(69420);
i128 extgcd(i128 a, i128 b, i128 &x, i128 &y){
if (b == 0){
x = 1;
y = 0;
return a;
}
i128 x0, y0;
i128 g = extgcd(b, a%b, x0, y0);
x = y0;
y = x0-a/b*y0;
return g;
}
ll Bob(vector <pii> E){
if (!chk_Bob){
for (int i = 2; i <= NM; i++){
arr_Bob[i].clear();
for (int j = 0; j < i-1; j++) arr_Bob[i].push_back(j+1);
shuffle(arr_Bob[i].begin(), arr_Bob[i].end(), rng_Bob);
}
chk_Bob = 1;
}
K = 0;
for (pii p : E){
K++;
m[K] = p.se-1;
r[K] = 0;
while (arr_Bob[p.se][r[K]] != p.fi) r[K]++;
}
for (int i = 2; i <= NM; i++)
for (int j = i; j <= NM; j += i)
if (f[j] == 0) f[j] = i;
for (int i = 2; i <= NM; i++) cur[i] = -1;
vector <int> arr;
for (int i = 1; i <= K; i++){
if (m[i] == 1) continue;
arr.clear();
int val = m[i];
while (val > 1){
if (arr.empty() || arr.back()%f[val] != 0) arr.push_back(f[val]);
else arr.back() *= f[val];
val /= f[val];
}
for (int y : arr) cur[y] = r[i]%y;
}
for (int i = 2; i <= NM; i++){
if (cur[i] == -1) continue;
bool chk = 0;
for (int j = i*2; j <= NM; j += i)
if (cur[j] != -1){
chk = 1;
break;
}
if (chk) cur[i] = -1;
}
vector <pll> T;
for (int i = 2; i <= NM; i++)
if (cur[i] != -1) T.push_back(mp(cur[i], i));
i128 a1 = T[0].fi, m1 = T[0].se;
for (int i = 1; i < isz(T); i++){
i128 a2 = T[i].fi, m2 = T[i].se;
i128 n1, n2, g = extgcd(m1, m2, n1, n2);
i128 res = (a1*n2*m2+a2*n1*m1)%(m1*m2);
if (res < 0) res += m1*m2;
a1 = res; m1 *= m2;
if (a1+m1 > LIM) break;
}
return (ll)a1;
}
