#include "xylophone.h"
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> pii;
int n;
int dnc(int s, int e) {
int m = (s + e) / 2;
int ret;
if ((ret = query(s, m)) == n - 1) return dnc(s, m);
else if (query(m + 1, e) == n - 1) return dnc(m + 1, e);
int i = s, j = m;
while (i < j) {
int d = (i + j + 1) / 2;
if (query(d, e) == n - 1) i = d;
else j = d - 1;
}
return i;
}
int q(int x, int y) {
static map<pii, int> mp;
if (mp.find(pii(x, y)) != mp.end()) return mp[pii(x, y)];
return mp[pii(x, y)] = query(x, y);
}
static int a[5001];
void solve(int N) {
n = N;
a[1] = 0;
a[2] = q(1, 2);
for (int i = 2; i < n; ++i) {
if (q(i - 1, i + 1) != q(i - 1, i) + q(i, i + 1)) {
if (a[i - 1] < a[i]) a[i + 1] = a[i] - q(i, i + 1);
else a[i + 1] = a[i] + q(i, i + 1);
}
else {
if (a[i - 1] < a[i]) a[i + 1] = a[i] + q(i, i + 1);
else a[i + 1] = a[i] - q(i, i + 1);
}
}
int i = min_element(a + 1, a + (n + 1)) - a;
int j = min_element(a + 1, a + (n + 1), greater<int>()) - a;
if (i > j) {
for (int i = 1; i <= n; ++i) a[i] = -a[i];
}
int x = (*min_element(a + 1, a + (n + 1))) - 1;
for (int i = 1; i <= n; ++i) {
answer(i, a[i] - x);
}
}
