Description

Farmer John 的 N（1 ≤ N ≤ 10000）只奶牛正站在一条直线上接受检阅。他们由 1 到 N 编号。每一只奶牛都有一个用正整数表示的身高。你被告知最高奶牛的编号 I 和身高 H（1 ≤ H ≤ 1000000），但是其他奶牛的身高就不得而知了。

Farmer John提供了R（0 ≤ R ≤ 10000）条信息，每条信息用两个正整数 a 和 b 表示，意味着“a 能看到 b”，也就是说，b 的身高不会小于 a，而且两只奶牛之间所有奶牛逼的身高均严格小于 a 的身高。

对每只奶牛，请计算最大的可能身高，使之不违反给出的信息。数据保证，合理的身高一定存在。

Format

Input

第 1 行输入 4 个整数，分别表示 N，I，H，R，接下来 R 行每行输入两个整数 a 和 b。 .

Output

一共 N 行，第 i 行表示第 i 号奶牛的最大可能身高。

Samples

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

5
4
5
3
4
4
5
5
5