#include "xylophone.h"
#include <bits/stdc++.h>
std::map<int,int> cache;
int twc(int a1,int a2,int a3){
return std::max(std::max(std::abs(a1-a2),std::abs(a2-a3)),std::abs(a1-a3));
}
void doAnswer(int i,int a){
std::cout << i << ' ' << a << '\n';
answer(i,a);
}
void solve(int N) {
int l=2,r=N;
int range=query(1,N);//i suppose this is always N-1
//find highest
while(l<r){
int mid=(l+r)/2;
if(query(1,mid)==range){
r=mid;
}
else{
l=mid+1;
}
}
int high=r;
doAnswer(high,N);
cache[N]=high;
if(high!=N){
int plast = N;
int last = N-query(high,high+1);
doAnswer(high+1,last);
for(int i=high+2;i<=N;i++){
int diff = query(i-1,i);
int n1 = last+diff,n2 = last-diff;
if(cache.find(n1)!=cache.end()||n1>N){
plast=last;
last=n2;
cache[n2]=i;
doAnswer(i,n2);
}
else if(cache.find(n2)!=cache.end()||n2<1){
plast=last;
last=n1;
cache[n1]=i;
doAnswer(i,n1);
}
else{
int value = query(i-2,i);
if(twc(plast,last,n1)==value){
plast=last;
last=n1;
cache[n1]=i;
doAnswer(i,n1);
}
else if(twc(plast,last,n2)==value){
plast=last;
last=n2;
cache[n2]=i;
doAnswer(i,n2);
}
else std::cout << "R";
}
}
}
if(high!=1){
//std::cout << "SMTH";
int plast = N;
int last = N-query(high-1,high);
doAnswer(high-1,last);
for(int i=high-2;i>=1;i--){
int diff = query(i,i+1);
int n1 = last+diff,n2 = last-diff;
if(cache.find(n1)!=cache.end()||n1>N){
plast=last;
last=n2;
cache[n2]=i;
doAnswer(i,n2);
}
else if(cache.find(n2)!=cache.end()||n2<1){
plast=last;
last=n1;
cache[n1]=i;
doAnswer(i,n1);
}
else{
int value = query(i,i+2);
if(twc(plast,last,n1)==value){
plast=last;
last=n1;
cache[n1]=i;
doAnswer(i,n1);
}
else if(twc(plast,last,n2)==value){
plast=last;
last=n2;
cache[n2]=i;
doAnswer(i,n2);
}
else std::cout << "L";
}
}
}
}
//5 3 2 1 5 4
