#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()
map<pii, int> rem;
int req(int l, int r)
{
if (rem[{l, r}])
return rem[{l, r}];
return rem[{l, r}] = query(l + 1, r + 1);
}
void solve(int n)
{
{
vector<int> a(n);
a[0] = 0;
a[1] = req(0, 1);
int p = 0;
for (int i = p + 2; i < n; ++i)
{
int v1 = req(i - 2, i);
int v2 = req(i - 1, i);
int mx = max(a[i - 2], a[i - 1]);
int mn = min(a[i - 2], a[i - 1]);
int d = mx - mn;
if (d == v1)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (v1 == v2)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (a[i - 1] == mn)
a[i] = a[i - 1] - v2;
else
a[i] = a[i - 1] + v2;
}
}
}
int mn = 0;
for (int i = 0; i < n; ++i)
mn = min(mn, a[i]);
for (int i = 0; i < n; ++i)
{
a[i] -= mn;
}
bool good = true;
vector<int> pos(n);
for (int i = 0; i < n; ++i)
{
if (0 <= a[i] and a[i] < n)
{
}
else
{
good = false;
break;
}
pos[a[i]] = i;
}
if (good and pos[0] < pos[n - 1])
for (int i = 1; i <= n; i++)
answer(i, a[i - 1] + 1);
}
{
vector<int> a(n);
a[0] = 0;
a[1] = -req(0, 1);
int p = 0;
for (int i = p + 2; i < n; ++i)
{
int v1 = req(i - 2, i);
int v2 = req(i - 1, i);
int mx = max(a[i - 2], a[i - 1]);
int mn = min(a[i - 2], a[i - 1]);
int d = mx - mn;
if (d == v1)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (v1 == v2)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (a[i - 1] == mn)
a[i] = a[i - 1] - v2;
else
a[i] = a[i - 1] + v2;
}
}
}
int mn = 0;
for (int i = 0; i < n; ++i)
mn = min(mn, a[i]);
for (int i = 0; i < n; ++i)
a[i] -= mn;
bool good = true;
vector<int> pos(n);
for (int i = 0; i < n; ++i)
{
if (0 <= a[i] and a[i] < n)
{
}
else
{
good = false;
break;
}
pos[a[i]] = i;
}
if (good and pos[0] < pos[n - 1])
for (int i = 1; i <= n; i++)
answer(i, a[i - 1] + 1);
}
}
