牛的最高身高

• 时间限制：C/C++ 200MS，其他语言 400MS
• 内存限制：C/C++ 8MB，其他语言 16MB

描述

$n$头牛站成了一排，依次编号为$1,2,...,n$，已知 $t$号牛最高（可能有其它牛一样高），身高为$h$。
此外，还有$R$条信息，每条信息包含两个整数$a,b$，表示：$a$号牛的身高$≤b$号牛的身高，且$a$号牛与$b$号牛之间所有牛（如果有的话）的身高都低于$a$号牛。
请推测出：每头牛的身高最高为多少？

输入描述

第$1$行，包含$4$个整数$n,t,h,R$
接下来$R$行，每行包含$2$个整数$a,b$，代表一条信息
【测试数据范围】$1 \le h \le 10^6,0 \le R \le 10^4,a \ne b$\

• 对于前$10$个测试点：$1 \le n \le 10^4$
• 对于第$11$个测试点：$n=50000$
• 测试数据保证答案存在，$R$条信息之间不会有互相矛盾的情况
• R 条信息不保证无重复

输出描述

输出$n$行，每行$1$个整数，依次代表$1,2,3,...,n$号牛的身高最高为多少

用例输入

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

用例输出

5
4
5
3
4
4
5
5
5