#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int used=0;
int colour[nmax]={0,1,2,3,3,1,2,4,4};
int cnt[nmax];
bool in[nmax];
int CURRENT;
/*
int Query(int pos)
{
used++;
CURRENT=CURRENT-(cnt[colour[pos]]>0);
if(in[pos])
{
in[pos]=0;
cnt[colour[pos]]--;
}
else
{
in[pos]=1;
cnt[colour[pos]]++;
}
CURRENT=CURRENT+(cnt[colour[pos]]>0);
return CURRENT;
}
void Answer(int a,int b)
{
return;
cout<<a<<" "<<b<<endl;
}
*/
mt19937 rng(42);
vector< pair<int,int> > outp;
int current=0;
int which_is_active(int le,int ri)
{
if(le)return 0;
return 1;
}
const int MX=1000;
int opt[MX]={0,0,1,1,1,1,1,3,3,1};
double exp_time[MX][MX];
double dp_time[MX];
double coeff=/*(1+sqrt(5))/2+1*/2.6246;
void solve(vector<int> lhs,vector<int> rhs,bool active_lhs)
{
shuffle(rhs.begin(),rhs.end(),rng);
if(lhs.size()==1)
{
outp.push_back({lhs[0],rhs[0]});
return;
}
int mid=lhs.size()/2;
if(lhs.size()<MX)mid=opt[lhs.size()];
else mid=lhs.size()/coeff;
vector<int> lhs_new[2],rhs_new[2];
lhs_new[0]={};lhs_new[1]={};
rhs_new[0]={};rhs_new[1]={};
for(int i=0;i<mid;i++)
{
int mem=Query(lhs[i]);
current=mem;
lhs_new[0].push_back(lhs[i]);
}
for(int i=mid;i<lhs.size();i++)
lhs_new[1].push_back(lhs[i]);
bool type_lhs[2]={!active_lhs,active_lhs};
for(auto k:rhs)
{
if(rhs_new[0].size()==lhs_new[0].size())rhs_new[1].push_back(k);
else if(rhs_new[1].size()==lhs_new[1].size())rhs_new[0].push_back(k);
else
{
int mem=Query(k);
if(current==mem)rhs_new[which_is_active(type_lhs[0],type_lhs[1])].push_back(k);
else rhs_new[!which_is_active(type_lhs[0],type_lhs[1])].push_back(k);
current=mem;
}
}
solve(lhs_new[0],rhs_new[0],type_lhs[0]);
solve(lhs_new[1],rhs_new[1],type_lhs[1]);
}
void Solve(int n)
{
for(int r=1;r<MX;r++)
for(int b=1;b<MX;b++)
{
exp_time[r][b]=1+exp_time[r-1][b]*r/(r+b)+exp_time[r][b-1]*b/(r+b);
}
for(int n_now=2;n_now<MX;n_now++)
{
dp_time[n_now]=1e9;
for(int mid=1;mid<n_now;mid++)
{
double now=dp_time[mid]+dp_time[n_now-mid]+mid+exp_time[mid][n_now-mid];
if(dp_time[n_now]>now)
{
opt[n_now]=mid;
dp_time[n_now]=now;
}
}
}
vector<int> lhs={},rhs={};
for(int i=1;i<=2*n;i++)
{
int mem=Query(i);
if(current<mem)lhs.push_back(i);
else rhs.push_back(i);
current=mem;
}
solve(lhs,rhs,1);
for(int i=0;i<n;i++)
Answer(outp[i].first,outp[i].second);
}
/*
int n;
void create()
{
for(int i=1;i<=n;i++)
colour[i]=i;
for(int i=n+1;i<=2*n;i++)
colour[i]=i-n;
shuffle(colour+1,colour+2*n+1,rng);
}
int main()
{
n=4.3e4;
create();
Solve(n);
cout<<"used= "<<used<<endl;
return 0;
}
*/
