Background

Description

N个士兵排成一排（从1到N标号）。最高的士兵（之一）标号为I，身高为H。YZM提供了R条 信息，每条信息描述Ai号士兵能看到Bi号士兵，这意味着Bi号士兵身高大等于Ai号士兵且他 们之间的士兵身高小于Ai号士兵。 现在对于N个士兵。依次输出最高的合法身高。

Format

Input

第一行四个数字N,I,H,R。 接下来R行，每行两个数字，Ai，Bi。 1<=N<=100000 0<=R<=10000

Output

N行，每行一个数字，按标号依次输出最高的合法身高。

Samples

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

5
4
5
3
4
4
5
5
5

Limitation

1s, 1024KiB for each test case.