Description

n 个⼈站⼀排，从左到右编号为 1 到 n，第 i 个⼈的身⾼是正整数 hi。

现已知身⾼最⾼者身⾼是 H，并有 r 组关系，每组包含两个数 a, b, 表示编号为 a 的能看到编号为 b 的。

a 能看到 b 的条件是 a 和 b 之间的身⾼都小于 min(ha, hb)。

请输出所有⼈身⾼的可能的最⼤值。

保证有合法解。

Format

Input

第 1 ⾏输⼊ 3 个数 n, H 和 r，之后 r ⾏⼀⾏输⼊⼀组 a,b。

Output

输出 n ⾏，每⾏ 1 个数字，表示每个⼈的身⾼最⼤值。

Samples

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

5
4
5
3
4
4
5
5
5

Limitation

不要在意⼈的身⾼到底有没有那么⾼。

关系可能重复出现。

对于 30% 数据，1 ≤ n ≤ 20, 1 ≤ H ≤ 20, 1 ≤ r ≤ 15

对于 100% 数据，1 ≤ n ≤ 5000, 1 ≤ H ≤ 7500, 1 ≤ r ≤ 10000