蜘蛛夏洛特坐在她蜘蛛网的中心，蜘蛛网由一系列从中心延伸到外边界的丝状直线组成。夏洛特的网上还有一些桥，每一座桥连接两条相邻的丝。桥的两个端点到蜘蛛网中心的距离总是相等的。

当夏洛特在中心享用完深夜盛宴并想退回到某个角落时，她会以自动导航模式走向边缘。为此，她会选择一条起始丝，并沿着它走，直到遇到该丝上的第一座桥。她会穿过这座桥到达另一条丝，然后继续向外走，直到遇到下一座桥。接着她会穿过那座桥，并重复这个过程，直到当前丝上没有更多的桥，然后她会走到当前丝的末端。注意，夏洛特必须穿过她遇到的所有桥。图 I.1 展示了夏洛特可能采取的一条路径。

夏洛特白天最喜欢睡觉的角落位于丝 $s$ 的末端。对于每一条可能的起始丝，她想知道为了最终到达 $s$，最少需要向原始蜘蛛网中添加多少座桥。夏洛特可以在丝上的任何位置添加桥，只要添加的桥不接触任何其他桥即可。任何添加的桥的两个端点到蜘蛛网中心的距离必须相等，且该桥必须连接两条相邻的丝。

图 I.1：样例输入 1 中从丝 4 开始的路径。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $s$，其中 $n$ ($3 \le n \le 200\,000$) 是丝的数量，$m$ ($0 \le m \le 500\,000$) 是桥的数量，$s$ ($1 \le s \le n$) 是夏洛特最喜欢的丝。丝按逆时针方向从 $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$ 所需添加的最少桥的数量。

样例

样例输入 1

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

样例输出 1

2
1
1
1
0
1
2

样例输入 2

4 4 2
1 1
2 2
3 3
4 4

样例输出 2

1
1
0
1