#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
mt19937 rd(1919810);
int bit[5010],tr[5010],now=0;
pair<int,int> sid[5010];
vector<int> ibit[70];
vector<pair<int,int>> ret;
queue<int> Q;
void init()
{
   srand(114514);
   for(int i=3;i<=5000;i++)
   {
      bit[i]=rand()%60;
      tr[i]=rand()%2+1;
   }
   for(int i=3;i<=5000;i++) ibit[bit[i]].push_back(i);
   return;
}
void print()
{
   shuffle(sid+1,sid+1+now,rd);ret.clear();ret.push_back({1,2});
   for(int i=1;i<=now;i++) ret.push_back({sid[i].first,sid[i].second});
   return;
}
vector<std::pair<int, int>> Alice()
{
   ll X,d;
   init();
   X=setN(5000);
   while(X)
   {
      d=__lg(X);
      Q.push(d);
      X-=(1ll<<d);
   }
   for(int i=59;i>=0;i--)
   {
      if(i==Q.front())
      {
         Q.pop();
         for(auto to:ibit[i]) sid[++now]={to,tr[to]};
         continue;
      }
      for(auto to:ibit[i]) sid[++now]={to,3-tr[to]};
   }
   print();
   return ret;
}

#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int bit2[5010],tr2[5010],res2[70];
ll calc()
{
   ll ans=0,dd=1;
   for(int i=0;i<=59;i++)
   {
      if(res2[i]) ans+=dd;
      dd*=2ll;
   }
   return ans;
}
void init2()
{
   srand(114514);
   for(int i=3;i<=5000;i++)
   {
      bit2[i]=rand()%60;
      tr2[i]=rand()%2+1;
   }
   return;
}
long long Bob(std::vector<std::pair<int, int>> V)
{
   init2();
   int m,x,y;
   for(int i=0;i<V.size();i++)
   {
      x=V[i].first;y=V[i].second;
      if(x==1) continue;
      if(tr2[x]==y) res2[bit2[x]]=1;
   }
   return calc();
}