#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int v[10000][2],q[5001][5001],cnt[5001];
void solve(int N) {
v[1][0] = 1;
q[1][2] = query(1,2);
v[2][0] = 1 + q[1][2];
v[1][1] = N;
v[2][1] = N - q[1][2];
for (int i = 3; i <= N;++i) {
q[i - 2][i] = query(i - 2,i);
q[i - 1][i] = query(i - 1,i);
}
for (int b = 0; b < 2;++b)
for (int i = 3; i <= N;++i) {
int a = q[i - 2][i];
int d = abs(v[i - 1][b] - v[i - 2][b]);
if (d == a) {
int dif = q[i - 1][i];
if (v[i - 1][b] > v[i - 2][b]) {
v[i][b] = v[i - 1][b] - dif;
}
else
v[i][b] = v[i - 1][b] + dif;
}
else {
int r = abs(v[i - 1][b] - v[i - 2][b]);
int dif = q[i - 1][i];
if (dif + r == a) {
if (v[i - 1][b] > v[i - 2][b])
v[i][b] = v[i - 1][b] + dif;
else
v[i][b] = v[i - 1][b] - dif;
}
else {
if (v[i - 2][b] > v[i - 1][b])
v[i][b] = v[i - 1][b] + dif;
else
v[i][b] = v[i - 1][b] - dif;
}
}
}
for (int b = 0; b < 2;++b) {
int mn = v[1][b];
for (int i = 1; i <= N;++i)
mn = min(mn,v[i][b]);
for (int i = 1; i <= N;++i) {
v[i][b] -= (mn - 1);
//cout << v[i][b] << ' ';
cnt[v[i][b]]++;
if (v[i][b] == N) {
if (cnt[1] == 0) {
cnt[N] = 0;
}
}
}
bool ok = true;
for (int i = 1; i <= N;++i) {
if (cnt[i] == 0) {
ok = false;
}
cnt[i] = 0;
}
if (ok) {
for (int i = 1; i <= N;++i)
answer(i,v[i][b]);
return;
}
}
}
