测试数据来自 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

【样例解释】

　　输入信息告诉我们，最高是1号，高为7。
　　根据前三条信息，1能看见2，所以2的身高不比1矮，所以2最高为7。又因为2能看见4，所以4最高也为7，而3在2，4之间，所以3最高为6。
　　再根据后三条信息，5也能看见8，所以8最高为7，5最高也为7，因为6、7在5和8之间，所以他们的身高最高为6，但7又在6和8之间，所以7比6矮，所以7最高为5，而6最高为6。

【数据说明】

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

【来源】

　　Mr.he