#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
// static int A[5000];
const int M = 1e5+5;
int sm[M], ans[M];
map<pair<int, int>, int> mp;
int cry(int a, int b) {
if (a == b) return 0;
if (!mp[{a, b}]) mp[{a, b}] = query(a, b);
return mp[{a, b}];
}
void solve(int n) {
sm[1] = 0;
for (int i = 1; i <= n-2; i++) {
int a = cry(i, i+1);
int b = cry(i+1, i+2);
int c = cry(i, i+2);
if (a + b == c) sm[i+1] = sm[i];
else sm[i+1] = !sm[i];
}
ans[1] = 0;
for (int i = 1; i < n; i++) {
if (sm[i]) ans[i+1] = ans[i] - cry(i, i+1);
else ans[i+1] = ans[i] + cry(i, i+1);
}
int mn = *min_element(ans+1, ans+n+1)-1;
for (int i = 1; i <= n; i++) ans[i] -= mn;
if (min_element(ans+1, ans+n+1)-ans > max_element(ans+1, ans+n+1)-ans) {
for (int i = 1; i <= n; i++) ans[i] = n+1-ans[i];
}
for (int i = 1; i <= n; i++) answer(i, ans[i]);
}
