题目描述

Farmer John 的 $N$ 只奶牛正站在一条直线上接受检阅。它们由 $1$ 到 $N$ 编号。每一只奶牛都有一个用正整数表示的身高。你被告知最高奶牛的编号 $I$ 和身高 $H$，但是其他奶牛的身高就不得而知了。

Farmer John 提供了 $R$ 条信息，每条信息用两个正整数 $a$ 和 $b$ 表示，意味着“$a$ 能看到 $b$”，也就是说，$b$ 的身高不会小于 $a$，而且两只奶牛之间所有奶牛的身高均严格小于 $a$ 的身高。

对每只奶牛，请计算最大的可能身高，使之不违反给出的信息。数据保证，合理的身高一定存在。

输入格式

第 $1$ 行输入 $4$ 个整数，分别表示 $N,I,H,R$。接下来 $R$ 行，每行输入两个整数 $a$ 和 $b$。

输出格式

一共 $N$ 行，第 $i$ 行表示第 $i$ 号奶牛的最大可能身高。

输入数据 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

输入数据 2

3 2 10 0

输出数据 2

10
10
10

输入数据 3

4 1 7 2
1 4
2 4

输出数据 3

7
6
5
7

数据范围与约定

$1\le N\le10000$，$1\le H\le1000000$，$0\le R\le10000$。