Description

N个小朋友笔直的排成一排，从左到右编号为1到N。他们的准确身高不能透漏给你，但是会告诉你这些小朋友中最高的身高是多少。然后给你R条信息，每条信息给出了A号小朋友能看到B号小朋友。“能看到”的定义是这样的：如果A能看到B，则B的身高大于或等于A的身高，而且处于A与B之间的那些小朋友的身高都小于A。现要你给出每个小朋友最高有可能的身高，而不会影响这R条信息的正确性。注：身高只能为整数值。

Input

输入包含多组测试数据。每组测试数据包含四个整数，N、H、R。 N表示小朋友的个数，H表示最高的身高，R表示信息的条数。接下来有R行，每行包含两个整数A、B，表示A能看到B。 1<=N<=10000,1<=H<=1000000,0<=R<=10000，1<=A,B<=N。

Output

针对每组测试数据，输出N行。第i行表示第i个小朋友有可能的最高身高。

Sample

Input

3 10 1
1 3

Output

10
9
10