Description
FJ的N（1 ≤ N ≤ 10,000） 头奶牛排成一排编号为1到N。每头奶牛都有一个身高，用一个正整数表示。你已经知道了最高的奶牛的高度是H(1≤H≤10^6)以及该奶牛的编号i.
同时FJ给出了R(0≤R≤10000)条记录信息，记录的格式是“奶牛17能看到奶牛34”，这条记录的意思是，奶牛34的高度至少与奶牛17的高度一样，而且从奶牛17到奶牛34之间的奶牛的高度严格小于奶牛17的高度。
满足所有给定信息仍然正确的情况下，分别给出1到N这N头奶牛可能的最大高度。
Input
第一行，四个整数分别为N i H 和R
接下来R行，每行表示一条记录，两个整数A和B，表示奶牛A能看到奶牛B。（1≤A,B≤N）
Output
输出N行，每行一个整数，分别表示N头奶牛可能的最大高度
9 3 5 5
1 3
5 3
4 3
3 7
9 8