[Usaco2007 Jan]Tallest Cow 最高的牛

农夫约翰的 $N$ 头牛排成一列，依次编号为 $1$ 到 $N$。每头牛的身高都是正整数，但具体数值未知。

已知最高的牛编号为 $I$，其身高为 $H$。此外，还有 $R$ 条关于牛之间视线关系的信息。每条信息包含两个不同的编号 $A$ 和 $B$，表示编号为 $A$ 的牛能够看到编号为 $B$ 的牛。这意味着：

• 编号为 $B$ 的牛的身高不低于编号为 $A$ 的牛；
• 编号严格位于 $A$ 和 $B$ 之间的每头牛，身高都严格低于编号为 $A$ 的牛。

请在满足所有已知信息的前提下，求出每头牛可能达到的最大身高。

保证所有给定条件可以同时满足。

输入格式

第一行包含四个以空格分隔的整数 $N$、$I$、$H$ 和 $R$，分别表示牛的数量、最高的牛的编号、最高身高以及视线关系的数量。

接下来 $R$ 行，每行包含两个不同的整数 $A$ 和 $B$，表示编号为 $A$ 的牛能够看到编号为 $B$ 的牛。

输出格式

输出 $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

数据范围

• $1\le N\le 10^4$；
• $1\le H\le 10^6$；
• $0\le R\le 10^4$；
• $1\le A,B\le N$，且 $A\ne B$；
• 每头牛的身高均为正整数。

来源与许可

本题为 USACO 2007 January 试题「Tallest Cow 最高的牛」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

5
4
5
3
4
4
5
5
5