题目描述

FarmerJohn 有 $n$ 头牛，它们按顺序排成一列。FarmerJohn 只知道其中最高的奶牛的序号及它的高度，其他奶牛的高度都是未知的。

FarmerJohn 手上有 $R$ 条信息，每条信息上有两头奶牛的序号（$a$ 和 $b$），其中 $b$ 奶牛的高度一定大于等于 $a$ 奶牛的高度，且 $a, b$ 之间的所有奶牛的高度都比 $a$ 小。

FarmerJohn 想让你根据这些信息求出每一头奶牛的可能的最大的高度。（数据保证有解）

输入格式

第一行包含四个以空格分隔的整数：$n, i, h, R$（$n$ 和 $R$ 意义见题面；$i$ 和 $h$ 表示第 $i$ 头牛的高度为 $h$，他是最高的奶牛）

接下来 $R$ 行：两个不同的整数 $a$ 和 $b$（$1 \le a, b \le n$）

输出格式

一共 $n$ 行，表示每头奶牛的最大可能高度.

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

5
4
5
3
4
4
5
5
5

数据规模与约定

对于全部的测试点，保证 $1 \le n \le 10000$，$1 \le h \le 1000000$，$0 \le R \le 10000$。