#include <bits/stdc++.h>
using namespace std;
//#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define endl '\n'
//#define int long long int
#define ll long long
#define NN 10000
#define carp 10000000
#define pb push_back
#define p push
#define ins insert
#define f first
#define s second
int query(int s,int t);
void answer(int i,int a);
/*int query(int s,int t){
cout<<s<<" "<<t<<endl;
int a;cin>>a;
return a;
}
void answer(int i,int a){
cout<<i<<" "<<a<<endl;
}*/
pair<vector<int>,vector<int>> arr[NN],seg[NN*4];
int deg[NN*4];
int val[NN];
void yap(int x,int b,int fark,int kim){
int okey_sol=0,okey_sag=0;
if(seg[x].f.size()==0)okey_sol=1;
if(seg[x].s.size()==0)okey_sag=1;
if(seg[x].f.size()){
for(auto u:seg[x].f){
if(u<0||u>fark){okey_sol=1;break;}
}
}
if(seg[x].s.size()){
for(auto u:seg[x].s){
if(u<0||u>fark){okey_sag=1;break;}
}
}
if(kim==1){
if(okey_sol)seg[x].f=seg[x*2].f;
if(okey_sag)seg[x].s=seg[x*2].s;
}
else{
if(okey_sol)seg[x].f=seg[x*2+1].f;
if(okey_sag)seg[x].s=seg[x*2+1].s;
if(okey_sol)reverse(seg[x].f.begin(),seg[x].f.end());
if(okey_sag)reverse(seg[x].s.begin(),seg[x].s.end());
reverse(seg[b].f.begin(),seg[b].f.end());
reverse(seg[b].s.begin(),seg[b].s.end());
}
if(okey_sol){
set<int> st;
int sonn=0;
for(auto u:seg[x].f){
sonn=u;
st.ins(u);
}
int ok=1,geld=1;
int son=sonn;
for(auto u:seg[b].f){
if(geld){
son-=u;
geld=0;continue;
}
int yeni=u+son;
if(st.find(yeni)!=st.end()||yeni<0||yeni>fark){
ok=0;break;
}
}
if(ok){
geld=1;
for(auto u:seg[b].f){
if(geld){geld=0;continue;}
seg[x].f.pb(u+son);
}
}
else{
geld=1;
for(auto u:seg[b].s){
if(geld){
sonn-=u;
geld=0;continue;
}
seg[x].f.pb(u+sonn);
}
}
}
if(okey_sag){
set<int> st;
int sonn=0;
for(auto u:seg[x].s){
sonn=u;
st.ins(u);
}
int ok=1,geld=1;
int son=sonn;
for(auto u:seg[b].f){
if(geld){
son-=u;
geld=0;continue;
}
int yeni=u+son;
if(st.find(yeni)!=st.end()||yeni<0||yeni>fark){
ok=0;break;
}
}
if(ok){
geld=1;
for(auto u:seg[b].f){
if(geld){geld=0;continue;}
seg[x].s.pb(u+son);
}
}
else{
geld=1;
for(auto u:seg[b].s){
if(geld){
sonn-=u;
geld=0;continue;
}
seg[x].s.pb(u+sonn);
}
}
}
if(kim!=1){
if(okey_sol)reverse(seg[x].f.begin(),seg[x].f.end());
if(okey_sag)reverse(seg[x].s.begin(),seg[x].s.end());
reverse(seg[b].f.begin(),seg[b].f.end());
reverse(seg[b].s.begin(),seg[b].s.end());
}
}
void bui(int x,int l,int r){
if(l>r)return;
if(l==r){
seg[x]=arr[l];
deg[x]=val[l];return;
}
int mid=(l+r)/2;
bui(x*2,l,mid);bui(x*2+1,mid+1,r);
deg[x]=query(l,r+1);
if(deg[x]!=deg[x*2+1])yap(x,x*2+1,deg[x],1);
if(deg[x]!=deg[x*2]) yap(x,x*2,deg[x],0);
/*cout<<x<<" "<<l<<" "<<r<<": "<<deg[x]<<endl;
for(auto u:seg[x].f)cout<<u<<" ";
cout<<endl;
for(auto u:seg[x].s)cout<<u<<" ";
cout<<endl<<endl; */
}
void solve(int N){
for(int i=1;i<N;i++){
int de=query(i,i+1);
arr[i]={{0,de},{de,0}};
val[i]=de;
}
bui(1,1,N-1);
int okey=0;
for(auto u:seg[1].f){
if(u==0){
okey=1;break;
}
if(u==N-1)break;
}
if(okey){
int i=1;
for(auto u:seg[1].f){
answer(i,u+1);
i++;
}
}
else{
int i=1;
for(auto u:seg[1].s){
answer(i,u+1);
i++;
}
}
}
/*signed main(){
lalala;
int n;cin>>n;
solve(n);
}*/
