测试数据来自 system/2872

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　幼儿园的 \(n\) 小朋友站成一排，并从左到右被编号为 \(1..n\)。每头小朋友的身高为正整数，其中最高一个小朋友编号为 \(k\) 和身高为 \(h\)。注意，身高为H的小朋友可能不止 \(k\) 一个。

　　现在告诉你 \(m\) 条信息，每条信息格式为 \(a\ b\)：表示 \(a\) 号小朋友能看到 \(b\) 号小朋友，即 \(b\) 号小朋友的身高 不低于 \(a\) 号小朋友的身高，并且在 \(a\) 号和 \(b\) 号之间的小朋友的身高都 严格低于 \(a\) 号小朋友的身高。

　　请你推算每个小朋友的最大可能的身高，我们保证给出的数据都是正确的，且一定有满足限制条件的解。

【输入格式】

　　第 \(1\) 行包含四个用空格分开的整数：\(n, k, h\) 和 \(m\)；
　　第 \(2..m+1\) 行：每行包含两个用空格分开的整数 \(a\) 和 \(b\)，表示小朋友 \(a\) 能看到小朋友 \(b\)。注意：\(1≤a,b≤n\)，且有可能 \(a\) 比 \(b\) 大。

【输出格式】

　　输出 \(n\) 行，第 \(i\) 行包含一个整数，表示第 \(i\) 号小朋友的可能的最大身高。

【输入输出样例】

　Input

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

　Output

7
7
6
7
7
6
5
7

【数据说明】

　　对于 \(100\%\) 的数据，\(1 ≤ n ≤ 10000\)，\(1 ≤ h ≤ 1000\)，\(0 ≤ m ≤ 10000\)

【来源】

　　Mr.he