题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

5
4
5
3
4
4
5
5
5

提示

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