#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 2
///Same idea of subtask 1 implementing binary search (N log N queries)
int memo[105][105];
int a[105];
int binarySearch(int type,int s,int t,int value)
{
int L=s;
int R=t;
if(type<=2){
int j=t-1;
while(L<=R){
int mid=(L+R)/2;
if(query(s,mid)!=value){
j=mid;
L=mid+1;
}
else
R=mid-1;
}
return j;
}
else{
int j=s+1;
while(L<=R){
int mid=(L+R)/2;
if(query(mid,t)!=value){
j=mid;
R=mid-1;
}
else
L=mid+1;
}
return j;
}
}
void goodRange(int type,int s,int t)
{
if(s==t) return;
if(type<=2){
if(a[t]!=0) t--;
if(s==t) return;
int value=query(s,t);
int j=binarySearch(type,s,t,value);
a[j+1]=(type==1)? a[s]+value : a[s]-value;
int nextType=(type==1)? 2 : 1;
goodRange(nextType,j+1,t);
goodRange(nextType+2,s,j+1);
}
else{
if(a[s]!=0) s++;
if(s==t) return;
int value=query(s,t);
int j=binarySearch(type,s,t,value);
a[j-1]=(type==3)? a[t]+value : a[t]-value;
int nextType=(type==3)? 4 : 3;
goodRange(nextType,s,j-1);
goodRange(nextType-2,j-1,t);
}
}
void solve(int N) {
int j=binarySearch(1,1,N,N-1);
a[j+1]=N;
goodRange(4,1,j+1);
goodRange(2,j+1,N);
for(int i=1;i<=N;i++){
answer(i,a[i]);
}
}
