Spider Walk

Image by FBR

When Charlotte has finished a late-night feasting in the center and wants to retreat to some corner, she walks to the edge on autopilot. To do this, she picks a starting strand, and walks along it until she meets the first bridge on that strand. She will cross the bridge and go to the other strand, and then keeps walking outwards until she meets another bridge. Then she will cross that bridge, and repeat this process, until there are no more bridges on the current strand, and then she will walk to the end of the current strand. Note that Charlotte must cross all the bridges that she meets. Figure 1 illustrates one path Charlotte could take.

Charlotte’s favorite corner to sleep in during the daytime is at the end of strand $s$. For each possible starting strand, she wants to know the minimum number of bridges to add to the original web in order to end at $s$. Charlotte can add a bridge at any point along the strand, as long as the added bridge does not touch any other bridge. The two endpoints of any added bridge must have the same distance to the center of the spiderweb, and the bridge must connect two adjacent strands.

Figure 1: The path starting from strand $4$ on the spiderweb in Sample Input 1.

Input

The first line of input has three integers $n$, $m$, and $s$, where $n$ ($3 \leq n \leq 200\, 000$) is the number of strands, $m$ ($0 \leq m \leq 500\, 000$) is the number of bridges, and $s$ ($1 \leq s \leq n$) is Charlotte’s favorite strand. Strands are labeled from $1$ to $n$ in counterclockwise order. Each of the remaining $m$ lines contains two integers $d$ and $t$ describing a bridge, where $d$ ($1 \leq d \leq 10^9$) is the bridge’s distance from the center of the spiderweb and $t$ ($1 \leq t \leq n$) is the first strand of the bridge in counterclockwise order. Specifically, if $1 \leq t < n$, then the bridge connects strands $t$ and $t + 1$. If $t = n$, then the bridge connects strands $1$ and $n$. All bridge distances $d$ are distinct.

Output

Output $n$ lines, where the $i^{\text {th}}$ line is the minimum number of bridges Charlotte needs to add in order to end at strand $s$ after walking on autopilot from strand $i$.

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