有 N 个整数构成的数列 A_1,A_2 \dots A_n，数列中每个数都是整数，但值未知，请通过下列的条件还原出该数列每个数的最大值。

1. 已知数列第 M 个数最大，该数的值为 X；
2. 已知 C 个区间 [i,j] ，每个区间两端的值一定满足 A_i \le A_j，且区间 [i,j] 中除了 i 和 j 两个位置的数以外，其余任意位置的数 A_k 一定满足 A_k \lt A_i。

请根据以上条件，求出数列中每个数的最大值。

第 1 行读入 4 个整数 N,M,X,C，含义如题所示；

接下来 C 行，每行读入 2 个整数 i,j 两数之间有一个空格；

输出 N 行，每行一个整数，代表恢复出来的数列每个数最大可能的值。

数据范围

对于 100\% 的数据 1 \le N \le 10000，1 \le M \le N，1 \le C \le 10000；

数据保证合法性，并保证根据数据一定有解。

东方博宜OJ

差分数学月赛