描述

在暑假的时候，冬瓜为了完成作业，想去看一部电影。看的是什么呢？和谁看的呢？这我就不说了。咳咳，但是呢，由于排队的人超级多，冬瓜十分地无聊，他在Cell Phone 上摇微信，问了其他人互相能看见谁。
已知如果第i 个人能看到第j 个人，那么第i 个人到第j 个人之间的人的身高小于第i 个人的身高，并且第j 个人的身高不小于第i 个人的身高。当然如果是冬瓜，那他能看见的人数就可想而知了……
冬瓜灵机一动，希望能知道每个人的最大可能的高度。
给定人的总数（包括冬瓜），第K 个人最高，且他的身高是H，还有R 条信息，第Ai个人能看到第Bi 个人。

格式

输入格式

第 1 行为四个整数N，K，H，R(1 ≤ N ≤ 10,000, 1 ≤ H ≤ 1,000,000, 1 ≤ R ≤ 10,000)。N 代表人的总数，K 代表最高的人的编号，H 代表最高的人的身高，R 代表给定信息的数量。
从第 2 行到第R+1 行，每行两个不相等的整数Ai 和Bi，表示Ai 能看到Bi。

输出格式

输出共N 行，第i 行代表第i 个人的最大身高。

样例1

样例输入1

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

样例输出1

5
4
5
3
4
4
5
5
5

限制

每个测试点1s。