题目描述

蜘蛛 Charlotte 位于她的蜘蛛网的中心，蜘蛛网由一系列丝质直线组成，这些直线都是从中心延伸到网的外部边界。Charlotte 的网也有桥，每个桥都连接着相邻的两根线。桥的两个端点到蜘蛛网中心的距离总是一样的。

当 Charlotte 在网的中心吃完了深夜的大餐，想要退到某个角落时，她会自动走到边缘。要做到这一点，她会选择一根起始线并沿着它走，直到她遇到该线上的第一座桥。她会通过这座桥，走到另一条线上，然后一直向外走，直到她遇到另一座桥。然后她会通过那座桥，重复这个过程，直到当前的线上不再有桥，然后她会走到当前线的尽头。请注意，Charlotte 必须通过她所遇到的所有桥。图 I.1 展示了 Charlotte 可能经过的一条路径。

Charlotte 白天最喜欢睡觉的角落是在线 $s$ 的末端。对于每条可能的起始线，她想知道为了在 $s$ 处结束，需要在原网上增加的桥的最少数量。Charlotte 可以在线上的任何一点增加一个桥，只要增加的桥不接触任何其他的桥。任何增加的桥的两个端点到蜘蛛网中心的距离必须相同，而且该桥必须连接相邻的两根线。

输入格式

第一行包含三个整数 $n,m,s$，其中 $n\ (3\le n\le 200\ 000)$ 表示线的条数，$m\ (0\le m\le 500\ 000)$ 表示桥的数量，$s\ (1\le s\le n)$ 是 Charlotte 最喜欢的线。线按逆时针顺序从 $1$ 到 $n$ 编号。接下来 $m$ 行，每行两个整数 $d$ 和 $t$，描述一座桥，其中 $d\ (1\le d\le 10^9)$ 表示这座桥到蛛网中心之间的距离，$t\ (1\le t\le n)$ 是按逆时针顺序数，桥第一端所在线的编号。具体地，如果 $1\le t<n$，那么这座桥连接线 $t$ 和 $t+1$。如果 $t=n$，那么这座桥连接线 $1$ 和 $n$。所有桥的距离 $d$ 互不相同。

输出格式

输出 $n$ 行，第 $i$ 行输出为了从线 $i$ 开始自动寻路，最终走到线 $s$，Charlotte 所需添加的最少的桥的个数。

7 5 6
2 1
4 3
6 3
8 7
10 5

2
1
1
1
0
1
2

4 4 2
1 1
2 2
3 3
4 4

1
1
0
1