Bajtolina 老师是 Bajtoły Dolne 第 64 小学的一名教师，她最近给学生们布置了一项家庭作业。学生们需要在 $n$ 天内记录城市当前的温度，然后汇总结果，并将所有记录的数字按顺序写成一行。

不幸的是，在交作业的前一天，大家发现只有 Alina 认真完成了作业。Alina 的同学 Kasia 请求她分享自己的结果。Alina 不情愿地同意了，但要求 Kasia 修改一些数据，以免看起来完全一样。于是，Kasia 抄写了结果，并将其中一个温度修改为另一个值。接着，Wojtek 抄写了 Kasia 的结果，也修改了其中一个温度；Mateusz 抄写了 Wojtek 的数据，Marcin 抄写了 Mateusz 的，Alojzy 抄写了 Marcin 的，Wiktoria 抄写了 Alojzy 的……最终，所有学生都有了各自版本的作业数据！

Bajtolina 老师收集了全班同学的作业纸。她决定在回家后查看这些测量数据，现在她只需要整理这些纸张。她决定按字典序排列它们——如果两张纸的初始部分相同，而纸张 A 上第一个不一致的温度值小于纸张 B 上对应的温度值，则纸张 A 排在纸张 B 之前。

Bajtolina 老师应该按什么顺序排列这些纸张？

输入格式

输入的第一行包含两个整数 $n, m$ ($1 \le n \le 500\,000, 2 \le m \le 500\,000$)，分别表示温度测量的天数和班级中的学生人数。学生按学号从 $1$ 到 $m$ 编号。

下一行包含一个由 $n$ 个整数组成的序列 $t_1, \dots, t_n$ ($0 \le t_i \le 10^9$)，这是 Alina 记录的温度测量值。假设 Alina 的学号为 $1$。

接下来的 $m - 1$ 行，每行包含两个整数 $p_i, x_i$ ($1 \le p_i \le n, 0 \le x_i \le 10^9$)；其中第 $i$ 行（对于 $i \ge 1$）表示学号为 $i + 1$ 的学生抄写了学号为 $i$ 的学生的数据，并将第 $p_i$ 天的温度修改为了 $x_i$。

输出格式

输出一行，包含 $m$ 个由空格分隔的整数，表示排序后的学生学号顺序。具体来说，如果序列中的第 $i$ 个数字是 $u_i$，则表示学号为 $u_i$ 的学生的作业纸在排序后排在第 $i$ 位。

如果两名学生的作业内容完全相同，则学号较小的学生排在前面。

样例

样例输入 1

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

样例输出 1

3 4 5 1 2 7 6 8