#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int n) {
int t[5002];
memset(t, 0, sizeof t);
int q[5][5002];
memset(q, 0, sizeof q);
q[0][2] = query(1, 2);
t[2] = q[0][2];
int e = min(t[1], t[2]);
for (int i = 3; i <= n; i ++) {
q[0][i] = query(i-1, i);
q[1][i] = query(i-2, i);
if (t[i-2] < t[i-1]) {
if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] - q[0][i];
else t[i] = t[i-1] + q[0][i];
}
else {
if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] + q[0][i];
else t[i] = t[i-1] - q[0][i];
}
e = min(e, t[i]);
}
int bio[5002];
memset(bio, 0, sizeof bio);
int p = 0;
int ne = 0;
for (int i = 1; i <= n; i ++) {
t[i] -= e-1;
if (t[i] >= 1 && t[i] <= n) bio[t[i]] ++;
if (t[i] == 1) p = 1;
if (t[i] == n && p == 0) {
ne = 1;
}
}
int da = 1;
for (int i = 1; i <= n; i ++) {
if (bio[i] != 1) {
da = 0;
break;
}
}
if (da == 1 && ne == 0) {
for (int i = 1; i <= n; i ++) {
answer(i, t[i]);
}
return;
}
memset(t, 0, sizeof t);
t[2] = -q[0][2];
e = min(t[1], t[2]);
for (int i = 3; i <= n; i ++) {
if (t[i-2] < t[i-1]) {
if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] - q[0][i];
else t[i] = t[i-1] + q[0][i];
}
else {
if (q[0][i] == q[1][i] || q[0][i-1] == q[1][i]) t[i] = t[i-1] + q[0][i];
else t[i] = t[i-1] - q[0][i];
}
e = min(e, t[i]);
}
memset(bio, 0, sizeof bio);
p = 0;
ne = 0;
for (int i = 1; i <= n; i ++) {
t[i] -= e-1;
if (t[i] >= 1 && t[i] <= n) bio[t[i]] ++;
if (t[i] == 1) p = 1;
if (t[i] == n && p == 0) {
ne = 1;
}
}
da = 1;
for (int i = 1; i <= n; i ++) {
if (bio[i] != 1) {
da = 0;
break;
}
}
if (da == 1 && ne == 0) {
for (int i = 1; i <= n; i ++) {
answer(i, t[i]);
}
return;
}
assert(0);
}
