#include "xylophone.h"
#include "bits/stdc++.h"
static int A[5001];
void solve(int N){
int l = 1, r = N;
bool use[N + 1];
for(int i = 1; i <= N; i++)
use[i] = 0;
while(r - l > 1){
int mid = (l + r) / 2;
if(query(1, mid) == N - 1)
r = mid;
else
l = mid;
}
A[r] = N;
use[N] = 1;
int x = query(r - 1, r);
A[r - 1] = N - x;
use[N - x] = 1;
if(r != N){
x = query(r, r + 1);
A[r + 1] = N - x;
use[N - x] = 1;
}
for(int i = r - 2; i >= 1; i--){
x = query(i, i + 1);
if(A[i + 1] - x <= 0){
A[i] = A[i + 1] + x;
use[A[i + 1] + x] = 1;
continue;
}
if(A[i + 1] + x > N){
A[i] = A[i + 1] - x;
use[A[i + 1] - x] = 1;
continue;
}
if(use[A[i + 1] + x]){
A[i] = A[i + 1] - x;
use[A[i + 1] - x] = 1;
continue;
}
if(use[A[i + 1] - x]){
A[i] = A[i + 1] + x;
use[A[i + 1] + x] = 1;
continue;
}
int z = query(i, i + 2), y = abs(A[i + 1] - A[i + 2]);
if(!(z == x + y)){
if(A[i + 2] > A[i + 1]){
A[i] = A[i + 1] + x;
use[A[i + 1] + x] = 1;
}
else{
A[i] = A[i + 1] - x;
use[A[i + 1] - x] = 1;
}
}
else{
if(A[i + 2] > A[i + 1]){
A[i] = A[i + 1] - x;
use[A[i + 1] - x] = 1;
}
else{
A[i] = A[i + 1] + x;
use[A[i + 1] + x] = 1;
}
}
}
for(int i = r + 2; i <= N; i++){
x = query(i - 1, i);
if(A[i - 1] - x <= 0){
A[i] = A[i - 1] + x;
use[A[i - 1] + x] = 1;
continue;
}
if(A[i - 1] + x > N){
A[i] = A[i - 1] - x;
use[A[i - 1] - x] = 1;
continue;
}
if(use[A[i - 1] - x]){
A[i] = A[i - 1] + x;
use[A[i - 1] + x] = 1;
continue;
}
if(use[A[i - 1] - x]){
A[i] = A[i - 1] + x;
use[A[i - 1] + x] = 1;
continue;
}
int z = query(i - 2, i), y = abs(A[i - 1] - A[i - 2]);
if(!(z == x + y)){
if(A[i - 2] > A[i - 1]){
A[i] = A[i - 1] + x;
use[A[i - 1] + x] = 1;
}
else{
A[i] = A[i - 1] - x;
use[A[i - 1] - x] = 1;
}
}
else{
if(A[i - 2] > A[i - 1]){
A[i] = A[i - 1] - x;
use[A[i - 1] - x] = 1;
}
else{
A[i] = A[i - 1] + x;
use[A[i - 1] + x] = 1;
}
}
}
for(int i = 1; i <= N; i++)
answer(i, A[i]);
}
