#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int A[5005];
bool cant[5005];
set<int> poss[5005];
vector<int> all[5005];
void solve(int N) {
/*
int value = query(1, N);
for(int i = 1; i <= N; i++) {
answer(i, i);
}
*/
int low = 1,high = N;
// prefix
while(low != high){
int mid = (low+high)/2;
if(query(1,mid) == N-1){
high = mid;
}else low = mid+1;
}
int five = high;
low = 1, high = N;
while(low != high){
int mid = (low+high+1)/2;
if(query(mid,N) == N-1){
low = mid;
}else high = mid-1;
}
int one = low;
vector<int> A(N+1,0);
A[one] = 1;
A[five] = N;
cant[1] = 1;
cant[N] = 1;
poss[one].insert(1);
poss[five].insert(N);
int cnt = N-2;
for(int i=one-1;i>=1;i--){
int q = query(i,i+1);
if(A[i+1] != 0){
int nx = A[i+1]+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
nx = A[i+1]-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
}else
for(auto x:poss[i+1]){
int nx = x+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
nx = x-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
}
cerr<<i<<" "<<poss[i].size()<< '\n';
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
for(auto x:all[A[i]]){
poss[x].erase(A[i]);
}
}
}
for(int i=one+1;i<five-1;i++){
int q = query(i-1,i);
if(A[i-1] != 0){
int nx = A[i-1]+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
nx = A[i-1]-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
}else
for(auto x:poss[i-1]){
int nx = x+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
nx = x-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
}
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
for(auto x:all[A[i]]){
poss[x].erase(A[i]);
}
}
}
if(five-1 > one){
int q = query(five-1,five);
A[five-1]= N-q;
cant[A[five-1]] = 1;
poss[five-1].insert(A[five-1]);
for(auto x:all[A[five-1]]){
poss[x].erase(A[five-1]);
}
cnt--;
}
for(int i=five+1;i<=N;i++){
int q = query(i-1,i);
if(A[i-1] != 0){
int nx = A[i-1]+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
nx = A[i-1]-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
all[nx].push_back(i);
}
}else
for(auto x:poss[i-1]){
int nx = x+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);all[nx].push_back(i);
}
nx = x-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);all[nx].push_back(i);
}
}
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
for(auto x:all[A[i]]){
poss[x].erase(A[i]);
}
}
}
while(cnt){
for(int i=1;i<=N;i++){
vector<int> er;
for(auto x:poss[i]){
if(cant[x])er.push_back(x);
}
for(auto x:er)poss[i].erase(x);
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
for(auto x:all[A[i]]){
poss[x].erase(A[i]);
}
}
}
}
for(int i = 1; i <= N; i++) {
cerr<<i<<": ";
for(auto x:poss[i]){
cerr<<x<<" ";
}
cerr<<'\n';
}
for(int i = 1; i <= N; i++) {
cerr << A[i] << ' ';
}
for(int i = 1; i <= N; i++) {
answer(i, A[i]);
}
}
