Spider Walk

Charlotte the spider sits at the center of her spiderweb. The web consists of silken straight strands that go from the center to the outer boundary. Charlotte's web also has bridges, each connecting two adjacent strands. The two endpoints of a bridge are always the same distance from the center.

When Charlotte finishes a late-night feast at the center and wants to retreat to a corner, she walks to the edge on autopilot. She picks a starting strand and walks along it until she meets the first bridge on that strand. She crosses the bridge onto the other strand and keeps walking outward until she meets another bridge. She crosses that bridge too and repeats the process. When no bridges remain on the current strand, she walks to the end of it. Charlotte must cross all the bridges she meets. The figure shows one path Charlotte could take.

Figure I.1: The path starting from strand 4.

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 so that she ends at $s$. Charlotte can add a bridge at any point along a strand, as long as the added bridge does not touch any other bridge. The two endpoints of an added bridge must be the same distance from the center, and the bridge must connect two adjacent strands.

The first line has three integers $n$, $m$, and $s$, where $3 \le n \le 200000$ is the number of strands, $0 \le m \le 500000$ is the number of bridges, and $1 \le s \le 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 $1 \le d \le 10^9$ is the bridge's distance from the center and $1 \le t \le n$ is the first strand of the bridge in counterclockwise order. If $1 \le t < n$, the bridge connects strands $t$ and $t+1$. If $t = n$, the bridge connects strands $1$ and $n$. All bridge distances $d$ are distinct.

Output $n$ lines. The $i$-th line is the minimum number of bridges Charlotte needs to add so that she ends at strand $s$ after walking on autopilot from strand $i$.