#include "bits/stdc++.h"
#include "xylophone.h"
using namespace std;
#define pb push_back
void solve(int n)
{
/*orig.resize(n+1);
for(int i = 1; i<=n; i++)
cin >> orig[i];*/
vector<vector<int>> q(n+1, vector<int>(n+1, 0));
for(int i = 1; i<n; i++)
{
q[i][i+1] = query(i, i+1);
}
for(int i = 1; i<n-1;i++)
{
q[i][i+2] = query(i, i+2);
}
vector<int> arr(n+1);
arr[1] = 1;
for(int i = 1; i<n-1; i++)
{
if(q[i][i+2]==q[i][i+1]+q[i+1][i+2])
{
arr[i+1] = arr[i];
}
else
{
arr[i+1]-=arr[i];
}
}
for(int i = 1; i<n; i++)
{
arr[i]*=q[i][i+1];
}
vector<int> res(n+1);
res[1] = 1;
for(int i = 1; i<n; i++)
{
res[i+1] = res[i] + arr[i];
}
int mini = 1e9;
for(int i = 1; i<=n; i++)
mini = min(mini, res[i]);
for(int i = 1; i<=n; i++)
{
res[i]-=mini;
res[i]--;
}
bool flag = true;
int l = n, r = 1;
for(int i = 1; i<=n; i++)
{
if(res[i]<=0)
{
flag = false;
break;
}
if(res[i]==1)
l = i;
if(res[i]==n)
r = i;
}
if(l>=r)
flag = false;
if(flag)
{
for(int i = 1; i<=n; i++)
answer(i, res[i]);
}
else
{
//res.assign(n+1, 1);
for(int i = 1; i<n; i++)
res[i+1] = res[i] - arr[i];
int mini = 1e9;
for(int i = 1; i<=n; i++)
mini = min(mini, res[i]);
for(int i = 1; i<=n; i++)
{
res[i]-=mini;
res[i]--;
}
for(int i = 1; i<=n; i++)
mini = min(mini, res[i]);
int dif = 1 - mini;
for(int i = 1; i<=n; i++)
res[i]+=dif;
for(int i = 1; i<=n; i++)
answer(i, res[i]);
}
}
