Spiderweb Bridge Addition

Charlotte the spider sits at the center of her spiderweb. The web consists of n radial strands (numbered 1 through n arranged in a circle) and a set of m bridges. Each bridge is a straight silken thread that connects two adjacent strands and is given by a pair (u, d): if u is given then the bridge connects strand u and strand u+1 (with the special case that when u = n it connects n and 1). The number d is the radial distance from the center to the bridge; all bridges lie at distinct distances on a given strand and are accessed in increasing order of d.

When Charlotte leaves the center, she chooses one of the strands as her starting strand. She then walks outward along that strand. Whenever she reaches a bridge (i.e. the first bridge encountered—namely the one with the smallest distance larger than her current position) she must cross it to the adjacent strand. Her current radial position becomes the distance of that bridge, and she continues walking outward on the new strand. When no further bridge exists on the current strand, she exits at the outer boundary of that strand.

Charlotte’s favorite sleeping corner is at the end of a fixed strand s. For each possible starting strand (1 ≤ i ≤ n) she wishes to know the minimum number of additional bridges needed to be added so that, if she follows the above procedure, she will eventually exit at strand s. An added bridge must:

1. Connect two adjacent strands (i.e. if placed on strand i it connects i and one of its two adjacent neighbors);
2. Be placed at some radial distance, with the two endpoints having the same distance from the center;
3. Not touch any other (original or added) bridge (so it can be inserted arbitrarily in any gap).

You may assume that by placing added bridges at an arbitrarily small radial increment (without conflicting with any existing bridge), Charlotte can choose to cross an added bridge in place of an original bridge if she wishes. Thus, the problem reduces to: for every starting strand i, what is the minimum number of added bridges required so that, by optionally forcing an immediate switch (to one of the two adjacent strands) instead of following the natural (original) route, Charlotte eventually exits at strand s.

Observation: Let f(i) denote the final strand that Charlotte reaches when starting from strand i using only the original bridges. Notice that if f(i)=s then no bridge needs to be added. Otherwise, by adding a bridge at the start you can force an immediate change to one of the two adjacent strands. Repeating this process means that the minimum number of added bridges needed from a given starting strand i is exactly the minimum circular distance from i to any strand j such that f(j)=s.

More formally, let G be the set of strands satisfying f(j)=s. For a starting strand i, the answer is

You are given n, m, and s. Then m lines follow, each containing two integers u and d representing an original bridge (with u indicating that the bridge connects strand u and strand u+1, with the convention that if u = n the bridge connects n and 1), and d the distance from the center.

inputFormat

The first line contains three integers n, m, and s (2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵, 1 ≤ s ≤ n), representing the number of strands, the number of original bridges, and Charlotte’s favorite strand respectively.

Then m lines follow. Each of these m lines contains two integers u and d (1 ≤ u ≤ n, 1 ≤ d ≤ 10⁹). A line "u d" denotes an original bridge connecting strand u and strand u+1 (and if u = n it connects strand n and strand 1) at distance d from the center. It is guaranteed that on any given strand no two bridges share the same distance.

outputFormat

Output a single line containing n integers separated by spaces. The i-th integer represents the minimum number of added bridges required if Charlotte starts from strand i so that she exits at strand s.

sample

4 3 1
1 2
2 3
3 4

1 0 1 2