#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int a[5005];
int dp[5005][2], pos[5005], cnt[5005];
bool was[5005];
void solve(int n){
for(int i = 1; i < n; i++) dp[i][0] = query(i, i + 1);
for(int i = 1; i + 1 < n; i++) dp[i][1] = query(i, i + 2);
bool good = 0;
for(int r = 2; r <= n; r++){
for(int i = 1; i <= n; i++) was[i] = cnt[i] = pos[i] = a[i] = 0;
bool ok = 1;
int l = r - 1;
a[r] = n, was[a[r]] = 1;
a[l] = n - dp[l][0], was[a[l]] = 1;
if(r < n) a[r + 1] = n - dp[r][0], was[a[r + 1]] = 1;
for(int i = l - 1; i >= 1; i--){
a[i] = a[i + 1] - dp[i][0];
if(a[i] < 0 || a[i] > n || was[a[i]]){
a[i] = a[i + 1] + dp[i][0];
if(a[i] < 0 || a[i] > n || was[a[i]]){
ok = 0;
break;
}
was[a[i]] = 1;
continue;
}
if(dp[i][0] == abs(a[i + 1] - a[i])
&& dp[i][1] == max({a[i], a[i + 1], a[i + 2]}) - min({a[i], a[i + 1], a[i + 2]})
&& dp[i + 1][0] == abs(a[i + 2] - a[i + 1])){
was[a[i]] = 1;
continue;
}
a[i] = a[i + 1] + dp[i][0];
if(a[i] < 0 || a[i] > n || was[a[i]]){
ok = 0;
break;
}
was[a[i]] = 1;
}
if(!ok) continue;
for(int i = r + 2; i <= n; i++){
a[i] = a[i - 1] - dp[i - 1][0];
if(a[i] < 0 || a[i] > n || was[a[i]]){
a[i] = a[i - 1] + dp[i - 1][0];
if(a[i] < 0 || a[i] > n || was[a[i]]){
ok = 0;
break;
}
was[a[i]] = 1;
continue;
}
if(dp[i - 1][0] == abs(a[i] - a[i - 1])
&& dp[i - 2][1] == max({a[i], a[i - 1], a[i - 2]}) - min({a[i], a[i - 1], a[i - 2]})
&& dp[i - 2][0] == abs(a[i - 2] - a[i - 1])){
was[a[i]] = 1;
continue;
}
a[i] = a[i - 1] + dp[i - 1][0];
if(a[i] < 0 || a[i] > n || was[a[i]]){
ok = 0;
break;
}
was[a[i]] = 1;
}
if(!ok) continue;
for(int i = 2; i <= n; i++){
if(abs(a[i] - a[i - 1]) != dp[i - 1][0]) ok = 0;
if(i >= 3 && max({a[i], a[i - 1], a[i - 2]}) - min({a[i], a[i - 1], a[i - 2]}) != dp[i - 2][1]) ok = 0;
}
for(int i = 1; i <= n; i++) ok &= (a[i] <= n), ok &= (a[i] >= 1);
if(ok){
for(int i = 1; i <= n; i++) pos[a[i]] = i, cnt[a[i]]++;
for(int i = 1; i <= n; i++) ok &= (cnt[i] == 1);
ok &= (pos[1] < pos[n]);
}
if(ok){
good = 1;
break;
}
}
for(int i = 1; i <= n; i++){
answer(i, a[i]);
}
}
