Tallest Cow

FJ has N cows numbered 1 through N standing in a line. Each cow has a secret positive integer height. You are given the height H of the tallest cow along with its index I. Additionally, FJ recorded R observations of the form "cow A sees cow B". This means that:

• Cow B's height is at least the height of cow A.
• Every cow between A and B has a height strictly less than cow A.

Your task is to assign a maximum possible height to each cow such that all given observations are satisfied. It is guaranteed that at least one valid assignment exists.

The constraints are as follows:

• 1 ≤ N ≤ 10,000
• 1 ≤ H ≤ 1,000,000
• 0 ≤ R ≤ 10,000

Note: Observations between the same pair of cows should be counted only once.

Mathematically, if we denote the adjustment for each cow i as a prefix sum of differences, the final height for cow i is given by:

$$\text{height}(i) = H + \sum_{j=1}^{i} d_j,$$

where the difference array d is initialized with zeros and updated for each unique observation "cow A sees cow B" as follows:

• If A < B, then subtract 1 from each cow in the interval (A, B): update \(d_{A+1}\) by -1 and \(d_{B}\) by +1.
• If A > B, then treat the pair as \(min(A, B)\) and \(max(A, B)\) and update similarly.

The height of the cow at index I is fixed to be H.

inputFormat

The input begins with a single line containing four space-separated integers: N, I, H, and R.

Each of the next R lines contains two space-separated integers A and B indicating the observation "cow A sees cow B".

outputFormat

Output N lines. The i-th line should contain a single integer representing the maximum possible height of cow i under the given constraints.

sample

9 6 5 3
1 3
5 3
4 5

5
4
5
4
5
5
5
5
5

</p>