There are \(n\) people (numbered from \(1\) to \(n\)) signed up for a doctor's appointment. The doctor has to choose in which order he will appoint these people. The \(i\)-th patient should be appointed among the first \(p_i\) people. There are also \(m\) restrictions of the following format: the \(i\)-th restriction is denoted by two integers \((a_i, b_i)\) and means that the patient with the index \(a_i\) should be appointed earlier than the patient with the index \(b_i\).
For example, if \(n = 4\), \(p = [2, 3, 2, 4]\), \(m = 1\), \(a = [3]\) and \(b = [1]\), then the only order of appointment of patients that does not violate the restrictions is \([3, 1, 2, 4]\). For \(n =3\), \(p = [3, 3, 3]\), \(m = 0\), \(a = []\) and \(b = []\), any order of appointment is valid.
For each patient, calculate the minimum position in the order that they can have among all possible orderings that don't violate the restrictions.
Output
Print \(n\) integers, where \(i\)-th integer is equal to the minimum position of \(i\)-th patient in the order, among all valid orders. Positions in the order are numbered from \(1\) to \(n\).
Note
In the first example, \([3, 1, 2, 4]\) the only one valid order, so the minimum position of each patient is equal to their position in this order.
In the second example, any order is valid, so any patient can be appointed first.
In the third example, there are three valid orders: \([4, 2, 3, 1, 5]\), \([3, 4, 2, 1, 5]\) and \([4, 3, 2, 1, 5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
2 3 2 4
3 1
|
2 3 1 4
|
|
2
|
3 0
3 3 3
|
1 1 1
|
|
3
|
5 3
4 3 3 2 5
3 1
1 5
4 2
|
4 2 1 1 5
|