#include "rail.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
int n;
const int maxn = 5005;
int dist0[maxn];
int distu[maxn];
int distr[maxn];
int distl[maxn];
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
ii near = {1e9, 0};
for(int i = 1; i< n; i++)
{
dist0[i] = getDistance(0, i);
near = min(near, {dist0[i], i});
}
int u = near.Y;
vector<int> tol, tor;
tor.pb(u);
for(int i = 1; i< n; i++)
{
if(i == u) continue;
distu[i] = getDistance(u, i);
if(distu[i]> dist0[i]) tor.pb(i);
else tol.pb(i);
}
ii far = {0, 0};
for(int x : tor)
{
far = max(far, {dist0[x], x});
}
int T = far.Y, xt = far.X;
for(int x : tor)
{
if(x == u)
{
distr[u] = distu[T];
}
else distr[x] = getDistance(T, x);
}
distr[0] = dist0[T];
int buff = 0;
while(!tor.empty())
{
ii close = {1e9, 0};
vector<int> bad;
for(int x : tor)
{
close = min(close, {dist0[x], x});
}
int tag = close.Y;
// printf("tag = %d\n", tag);
location[tag] = dist0[tag];
// printf("%d->%d\n", tag, location[tag]);
stype[tag] = 2;
bool last = false;
if(distr[tag] == xt-location[tag])
{
T = tag;
xt = location[tag];
last = true;
}
for(int x : tor)
{
if(x == tag) continue;
int calc = dist0[x]-location[tag];
calc = location[tag]-calc;
if(buff< calc && calc< location[tag])
{
// if(tag == 11 && x == 8) printf("%d = %d\n", distr[x], xt+dist0[x]-2*location[tag]);
if(last || distr[x] == xt + dist0[x] - 2*location[tag])
{
location[x] = calc;
stype[x] = 1;
// printf("det'ed %d->%d\n", x, location[x]);
}
else
{
bad.pb(x);
}
}
else bad.pb(x);
}
tor = bad;
}
for(int i = 0; i< N; i++) location[i] += first;
stype[0] = 1;
for(int i = 0; i< N; i++) printf("%d %d\n", stype[i], location[i]);
}
