#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#define pb push_back
struct stat{
int loc, id, t;
};
const int MAXN = 5010;
int N;
vector<stat> b;
int dist[MAXN][MAXN];
/*int getDistance(int x, int y){
cout << "? " << x << ' ' << y << endl;
int z; cin >> z; return z;
}*/
int D(int x, int y){
if (dist[x][y] != -1) return dist[x][y];
if (x == y) return dist[x][y] = 0;
dist[y][x] = getDistance(x, y);
return dist[x][y] = dist[y][x];
}
bool cmp1(int x, int y){ return D(0, x) < D(0, y); }
bool cmp2(stat x, stat y){ return x.loc < y.loc; }
void findLocation(int n, int first, int location[], int stype[]){
memset(dist, -1, sizeof(dist)); N = n;
vector<int> a;
for (int i = 1; i < N; ++i) a.pb(i);
sort(a.begin(), a.end(), cmp1);
stat L = {first, 0, 0}, R = {first + D(0, a[0]), a[0], 1};
b.pb(L), b.pb(R);
for (int i = 1; i < (int)(a.size()); ++i){
int x = a[i];
//is he directly connected to L
int lx = L.loc + D(x, L.id);
//cout << " ??? " << x << ' ' << lx << " :: " << L.loc << ' ' << L.id << ' ' << L.t << " -- " << R.loc << ' ' << R.id << ' ' << R.t << endl;
bool good = 0;
for (auto p: b)
if (p.loc < min(lx, R.loc) && (lx - p.loc) + (R.loc - p.loc) == D(x, R.id)) good = 1;
if (good){
//cout << " !!! " << x << ' ' << lx << endl;
stat nw = {lx, x, 1}; b.pb(nw);
if (nw.loc > R.loc) R = nw;
}
else{
stat nw = {R.loc - D(x, R.id), x, 0}; b.pb(nw);
//cout << " !!! " << x << ' ' << nw.loc << endl;
if (nw.loc < L.loc) L = nw;
}
sort(b.begin(), b.end(), cmp2);
}
for (auto p: b){
//cout << "F: " << p.id << ": " << p.loc << ' ' << p.t << endl;
location[p.id] = p.loc, stype[p.id] = p.t;
}
/*for (int i = 0; i < N; ++i)
cout << location[i] << ' ';
cout << endl;
for (int i = 0; i < N; ++i)
cout << stype[i] << ' ';
cout << endl;*/
return;
}
int main(){
/*int niz[N] = { 0 };
findLocation(4, 2, niz, niz);*/
return 0;
}
