Description

FJ 的 $N$ 头奶牛（$1 \le N \le 10,000$）按编号 $1$ 到 $N$ 排成一行。每头奶牛有一个正整数表示的身高（这是个秘密）。现在你只知道最高奶牛的身高 $H$（$1 \le H \le 1,000,000$），以及它的编号 $I$。

FJ 提供了 $R$ 条信息（$0 \le R \le 10,000$），每条信息形如“奶牛 17 能看到奶牛 34”。这意味着奶牛 34 的身高不小于奶牛 17 的身高，并且编号在 17 和 34 之间的所有奶牛，其身高都严格小于奶牛 17 的身高。

现在请你计算出对于每一头奶牛（编号从 $1$ 到 $N$），在所有给定信息都成立的前提下，它可能具有的最大身高。

题目保证一定存在满足条件的解。

Input Format

第 $1$ 行：四个用空格分隔的整数：$N$，$I$，$H$ 和 $R$。

第 $2$ 到第 $R+1$ 行：每行两个不同的整数 $A$ 和 $B$（$1 \le A$, $B \le N$），表示奶牛 $A$ 能看到奶牛 $B$。

Output Format

共 $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