题目描述

有${n(1 <= n <= 10000)}$头牛从１到${n}$线性排列，每头牛的高度为${h[i](1 <= i <= n),}$

现在告诉你这里面的牛的最大高度为${maxH,}$而且有${r}$组关系，每组关系输入两个数字，

假设为${a}$和${b,}$表示第${a}$头牛能看到第${b}$头牛，能看到的条件是${a, b}$之间的其它牛的高度都严格小于${min(h[a], h[b]),}$而${h[b] >= h[a]}$

输入格式

第${1}$行：四个空格分隔整数：${N}$、${I}$、${H}$和${R}$

第${2...R+1}$行：两个不同的空间分隔整数${A}$和${B（}$${1<=A，}$${B<=N）}$，表示${cow A}$可以看到${cow B}$。

输出格式

第${1...N}$行： 第${i}$行包含奶牛${i}$的最大可能高度。

样例

输入样例

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

输出样例

5
4
5
3
4
4
5
5
5

提示

输入详细信息：有${9}$头奶牛，第三头是最高的，高${5}$。