#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "rail.h"
using namespace std;
struct Interactive
{
int n,i,j,k,u,v,node[1505],f[1505][1505];
void Init(int n,int x[],int type[])
{
for(i=0;i<n;i++) node[i]=i;
sort(node,node+n,[&](int u,int v){ return x[u]<x[v]; });
memset(f,63,sizeof(f));
for(u=0;u<n;u++) f[u][u]=0;
for(i=0;i<n;i++)
{
u=node[i];
for(j=i+1;j<n;j++)
{
v=node[j];
if(type[u]==1 && type[v]==2) f[u][v]=f[v][u]=x[v]-x[u];
}
}
for(k=0;k<n;k++)
for(u=0;u<n;u++)
for(v=0;v<n;v++) f[u][v]=min(f[u][v],f[u][k]+f[k][v]);
}
} IR;
int x[5005],type[5005],mask[1000005],n,i,u,v,dis0[5005],disk[5005],to_l,to_r,x0,k;
II a[5005];
/*
int getDistance(int u,int v)
{
// cerr<<u<<" "<<v<<'\n';
return IR.f[u][v];
}*/
void findLocation(int n,int x0,int x[],int type[])
{
auto add=[&](int u,int _x,int _type)
{
x[u]=_x;
type[u]=_type;
mask[x[u]]=type[u];
};
for(i=1;i<n;i++) a[i]={ getDistance(i,0),i };
sort(a+1,a+n);
add(0,x0,1);
add(a[1].snd,x0+a[1].fst,2);
k=a[1].snd;
for(i=0;i<n;i++)
{
dis0[a[i].snd]=a[i].fst;
if(i==k) disk[i]=0;
else if(i==0) disk[i]=a[1].fst;
else disk[i]=getDistance(i,k);
}
int l=0,r=k;
for(i=2;i<n;i++)
{
u=a[i].snd;
if(dis0[u]==disk[u]+dis0[k] && disk[u]<disk[0])
add(u,x[k]-disk[u],1);
else if(dis0[u]==disk[u]+dis0[k])
{
int tg=disk[u]-disk[l]-(to_l=getDistance(l,u));
int ttv=mask[x[l]-tg/2];
if(ttv==1) add(u,l+to_l,2);
else add(u,x[k]-disk[u],1);
}
else
{
int tg=dis0[u]-dis0[r]-(to_r=getDistance(r,u));
int ttv=mask[x[r]+tg/2];
if(ttv==2) add(u,r-to_r,1);
else add(u,x[0]+dis0[u],2);
}
if(x[l]>x[u]) l=u;
if(x[r]<x[u]) r=u;
}
}
/*
int main()
{
freopen("rail.inp","r",stdin);
freopen("rail.out","w",stdout);
cin>>n;
for(i=0;i<n;i++) cin>>type[i]>>x[i];
IR.Init(n,x,type);
x0=x[0];
memset(x,0,sizeof(x));
memset(type,0,sizeof(type));
findLocation(n,x0,x,type);
for(i=0;i<n;i++) cout<<x[i]<<" "<<type[i]<<'\n';
freopen("rail.inp","r",stdin);
cin>>n;
for(i=0;i<n;i++)
{
int T,X;
cin>>T>>X;
if(T!=type[i] || X!=x[i])
cerr<<i<<'\n';
}
}
*/
