Ms. Bajtolina, a teacher at Primary School No. 64 in Bajtoły Dolne, recently assigned homework to her students. The children were supposed to record the temperature in the city for $n$ days, then collect the results and write down all the obtained numbers in a row.

Unfortunately, on the eve of the homework submission, it turned out that only Alina had done the assignment diligently. Kasia, Alina's friend, asked her to share her results. Alina reluctantly agreed, but ordered her to change the data a little so they wouldn't look the same. So, Kasia copied the results, changing one of the temperatures to another. Then, Wojtek copied the results from Kasia, again changing one of the temperatures she had written down to another. Mateusz copied the data from Wojtek, Marcin from Mateusz, Alojzy from Marcin, Wiktoria from Alojzy... Eventually, all students had their own version of the data!

Ms. Bajtolina collected the result sheets from the entire group. She decided that she would review the children's measurements at home, and for now, she would just sort the sheets. She decided to arrange them in lexicographical order – sheet $A$ will come before sheet $B$ if the initial part of the records matches on both sheets, and the first temperature that differs on sheet $A$ is lower than the corresponding value on sheet $B$.

In what order should Ms. Bajtolina arrange the sheets?

Input

The first line of input contains two integers $n, m$ ($1 \le n \le 500\,000$, $2 \le m \le 500\,000$) representing the number of temperature measurements and the number of children in the class, respectively. The children are numbered with integers from $1$ to $m$ in the order they appear in the school register.

The next line contains a sequence of $n$ integers $t_1, \dots, t_n$ ($0 \le t_i \le 10^9$) – the consecutive temperature measurements made by Alina. We assume that Alina is number $1$ in the register.

The next $m - 1$ lines each contain two integers $p_i, x_i$ ($1 \le p_i \le n$, $0 \le x_i \le 10^9$); the $i$-th of these lines (for $i \ge 1$) means that the person numbered $i + 1$ in the register copied the data from the person numbered $i$, changing the result of the $p_i$-th day to $x_i$ in the process.

Output

The output should contain exactly one line containing a sequence of $m$ integers separated by single spaces – the order of the sheets after sorting them. More precisely, if the $i$-th of these numbers is equal to $u_i$, then the sheet of the person numbered $u_i$ will be the $i$-th in the order after sorting.

If two students submitted the same work, the work of the child with the lower number should be placed earlier.

Examples

Input 1

5 8
4 2 1 7 3
3 6
1 2
2 5
5 5
1 5
1 4
1 5

Output 1

3 4 5 1 2 7 6 8