测试数据来自 system/1466

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

---

【问题描述】

　　FJ的 \(N\) 头奶牛站成一排，并从左到右被编号为 \(1..N\)。每头奶牛都有一个正整数的身高，具体的值FJ暂时保密，但会告诉你它们当中最高的一头的编号 \(I\) 和身高 \(H\) 的值。

　　FJ制作一张包含 \(R\) 行的列表，每行的都是形如“第 \(17\) 号奶牛能看到第 \(34\) 号奶牛”，其意义是 \(34\) 号奶牛的身高不低于 \(17\) 号奶牛的身高，并且在 \(17\) 号和 \(34\) 号之间的奶牛的身高都严格低于 \(17\) 号奶牛的身高。

　　请你确定奶牛每头奶牛的最大可能的身高，我们保证给出的数据都是正确的，并且一定有满足限制条件的解。

【输入格式】

　　第 \(1\) 行：包含四个用空格分开的整数：\(N, I, H\) 和 \(R\)；
　　第 \(2..R+1\) 行：每行包含两个用空格分开的整数 \(A\) 和 \(B(1≤A,B≤N)\),表示奶牛 \(A\) 能看到奶牛 \(B\)

【输出格式】

　　第 \(1..N\) 行：第 \(i\) 行包含一个整数，表示第 \(i\) 头奶牛的最大身高。

【输入输出样例】

　Input

9 3 5 5
1 3
5 3
4 3
3 7
9 8

　Output

5
4
5
3
4
4
5
5
5

【数据说明】

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

【来源】

　　Mr.he