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