During the World Expo, the volume of air passenger traffic in Shanghai far exceeded normal levels, leading to frequent air traffic control issues. Recently, Little X was delayed at the airport twice for over two hours due to air traffic control. Little X was very dissatisfied with this.

On his way to Yantai this time, Little X unfortunately encountered air traffic control again. Consequently, Little X began to think about problems related to air traffic control.

Suppose there are $n$ delayed flights, numbered $1$ to $n$. The airport has only one runway, and all flights must take off in a certain order (this order is called the takeoff sequence). The takeoff index of a flight is defined as its position in the takeoff sequence, i.e., which number flight it is to take off.

There are two types of constraints on the takeoff sequence: Type 1 (Latest takeoff time constraint): The takeoff index of flight $i$ must not exceed $k_i$. Type 2 (Relative takeoff order constraint): There are some relative takeoff order constraints $(a, b)$, indicating that flight $a$ must take off earlier than flight $b$, meaning the takeoff index of flight $a$ must be less than the takeoff index of flight $b$.

The first problem Little X is considering is whether a feasible takeoff sequence can be calculated given these two types of constraints. The second problem is, considering both types of constraints, how to find the minimum possible takeoff index for each flight across all feasible takeoff sequences.

Input

The first line contains two positive integers $n$ and $m$, where $n$ is the number of flights and $m$ is the number of Type 2 constraints (relative takeoff order constraints).

The second line contains $n$ positive integers $k_1, k_2, \dots, k_n$.

The next $m$ lines each contain two positive integers $a$ and $b$, representing a relative takeoff order constraint $(a, b)$, where $1 \le a, b \le n$, indicating that flight $a$ must take off before flight $b$.

Output

The output consists of two lines.

The first line contains $n$ integers representing a feasible takeoff sequence, with adjacent integers separated by spaces. The input data guarantees that at least one feasible takeoff sequence exists. If there are multiple feasible solutions, output any one of them.

The second line contains $n$ integers $t_1, t_2, \dots, t_n$, where $t_i$ is the minimum possible takeoff index for flight $i$, with adjacent integers separated by spaces.

Examples

Input 1

5 5
4 5 2 5 4
1 2
3 2
5 1
3 4
3 1

Output 1

3 5 1 4 2
3 4 1 2 1

Input 2

5 0
3 3 3 5 5

Output 2

3 2 1 5 4
1 1 1 4 4

Note

In Example 1: The takeoff sequence 3 5 1 4 2 satisfies all constraints. All valid takeoff sequences are: 3 4 5 1 2, 3 5 1 2 4, 3 5 1 4 2, 3 5 4 1 2, 5 3 1 2 4, 5 3 1 4 2, 5 3 4 1 2. Due to the constraints (5, 1) and (3, 1), flight 1 can only be scheduled after flights 5 and 3, so its earliest takeoff time is 3. The same applies to other flights.

In Example 2: Although flights 4 and 5 have no relative takeoff order constraints, since flights 1, 2, and 3 must all be scheduled in the first 3 takeoffs, flights 4 and 5 can only be scheduled to take off at the earliest at position 4.

Constraints

For 30% of the data: $n \le 10$. For 60% of the data: $n \le 500$. For 100% of the data: $n \le 2,000$, $m \le 10,000$.