#include <bits/stdc++.h>
#include "rail.h"
#define gd getDistance
#define eb emplace_back
using namespace std;
void findLocation(int N, int first, int L[], int T[]) {
vector<int> D(N), S;
for (int i=1; i<N; i++) S.eb(i), D[i]=gd(0, i);
sort(S.begin(), S.end(), [&](int x, int y) { return D[x]<D[y]; });
int l=0, r=S[0];
L[l]=0, L[r]=D[r];
T[l]=1, T[r]=2;
map<int, int> M;
M[0]=1, M[D[r]]=2;
for (int i=1; i<N-1; i++) {
int n=S[i];
int d1=gd(l, n), d2=gd(r, n), d=L[r]-L[l];
int x=(d2-d1+d)/2;
if (x<=min(d, d2)&&M[L[r]-x]==1) {
int dn=L[l]+d1;
L[n]=dn;
T[n]=2;
M[dn]=2;
if (dn>L[r]) r=n;
}
else {
int dn=L[r]-d2;
L[n]=dn;
T[n]=1;
M[dn]=1;
if (dn<L[l]) l=n;
}
}
for (int i=0; i<N; i++) L[i]=L[i]+first;
for (int i=0; i<N; i++) printf("%d %d\n", L[i], T[i]);
}
