#include <vector>
#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t lll;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
static bool prime[5050];
std::vector<std::pair<int,int>> Alice(){
ll x = setN(5000);
for(ll i = 2 ; i <= 5000 ; i++)if(!prime[i]){
for(ll j = i*i ; j <= 5000 ; j+=i)prime[j]=1;
}
vector<pair<int,int>> ret;
ret.push_back({1,5000});
for(int i = 2, j = 0 ; i < 5000 ; i++){
if(!prime[i])j=i;
int r = x%j; if(!r)r=5000;
ret.push_back({i,r});
}
return ret;
}
#include <vector>
#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t lll;
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
const ll Lnf = 1e18;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
struct asdf{
lll a=0, p=0, q=0, r=0;
};
static bool prime[5050];
ll solve(vector<asdf> &v){
lll P = 1;
// for(auto [a,p,q,r] : v)P*=p, cout<<"(a,p) : "<<(ll)a<<", "<<(ll)p<<endl;
for(auto &[a,p,q,r] : v){
q = P/p;
for(ll i = 1 ; i < p ; i++)if(i*(q%p)%p == 1){r=i; break; }
// assert(r!=0);
}
lll ret = 0;
for(auto [a,p,q,r] : v){
ret += (lll)a*r*q;
}
ret %= P;
return (ll)ret;
}
long long Bob(std::vector<std::pair<int,int>> V){
for(ll i = 2 ; i <= 5000 ; i++)if(!prime[i]){
for(ll j = i*i ; j <= 5000 ; j+=i)prime[j]=1;
}
for(auto &[a,b] : V)if(b==5000 and a!=1)b=0, swap(a,b);
sort(all(V), [&](pair<int,int> a, pair<int,int> b){
if(a.second == b.second)return a.first < b.first;
return a.second < b.second;
});
lll P = 1;
vector<asdf> v;
for(ll i = 2, j = 0, k = 0 ; i < 5000 and P < Lnf ; i++){
if(!prime[i])j=i;
while(k < sz(V) and V[k].second == i){
if(sz(v) and v.back().p == j);
else{
P *= j;
v.push_back({V[k].first,j,0,0});
}
k++;
if(P>=Lnf)break;
}
}
return solve(v);
}
