海绵宝宝的N（1≤N≤10000）头三体人方便地索引1…N排成一行。每头三体人都有一个正整数的高度（这有点秘密）。你只会被告知最高三体人的身高H（1≤H≤1000000）以及该三体人的指数I。 海绵宝宝列出了“17头三体人看到34头三体人”形式的R（0≤R≤10000）行。这意味着三体人34至少和三体人17一样高，并且17至34之间的每头三体人的高度都严格小于三体人17的高度。 对于从1…N开始的每头三体人，确定其可能的最大高度，以便所有给出的信息仍然正确。保证有可能满足所有的约束条件。

第1行：四个空格分隔的整数：N、I、H和R 第2行…R+1：两个不同的空间分隔整数A和B（1≤A，B≤N），表明三体人A可以看到三体人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