题目描述

题目译自 PA 2017 Runda 3 Praca domowa

Bajtolina 女士是下拜托拉第 64 小学的老师，最近给学生们布置了一项家庭作业。孩子们需要在 $n$ 天内记录城市当前的温度，然后汇总结果并将所有测得的数值依次写下。

不幸的是，在作业提交的前一天，发现只有 Alina 认真完成了任务。Alina 的同学 Kasia 请求查看她的结果。Alina 不太情愿地同意了，但要求对数据稍作修改，以免看起来完全一样。于是，Kasia 抄写了结果，但将其中一个温度值改成了另一个值。接着，Wojtek 从 Kasia 那里抄写数据，又改动了她记录的一个温度值。Mateusz 从 Wojtek 那里抄写，Marcin 从 Mateusz 那里抄写，Alojzy 从 Marcin 那里抄写，Wiktoria 从 Alojzy 那里抄写……最终，每个学生都有了自己版本的数据！

Bajtolina 女士收集了全班的作业纸。她决定回家再仔细查看孩子们的测量结果，现在只对作业纸进行整理。她决定按字典序排列这些作业纸——作业纸 $A$ 排在作业纸 $B$ 之前，当两张纸的前部分记录一致，而第一个不同的温度值在作业纸 $A$ 上比作业纸 $B$ 上的对应值小。

请问 Bajtolina 女士应如何排列这些作业纸？

输入格式

输入数据的第一行包含两个整数 $n, m$ $(1 \leq n \leq 500000, 2 \leq m \leq 500000)$，分别表示温度测量的天数和班级中学生的数量。学生按照学籍记录的顺序编号为从 $1$ 到 $m$ 的整数。

第二行包含 $n$ 个整数 $t_{1}, \ldots, t_{n}$ $(0 \leq t_{i} \leq 10^{9})$，表示 Alina 记录的各天温度测量值。假设 Alina 在学籍记录中的编号为 $1$。

接下来的 $m-1$ 行每行包含两个整数 $p_{i}, x_{i}$ $(1 \leq p_{i} \leq n, 0 \leq x_{i} \leq 10^{9})$；第 $i$ $(i \geq 1)$ 行表示学籍编号为 $i+1$ 的学生从编号为 $i$ 的学生那里抄写了数据，并将第 $p_{i}$ 天的测量结果改为 $x_{i}$。

输出格式

输出应包含一行，包含 $m$ 个用单个空格分隔的整数——排列后的作业纸顺序。具体来说，如果第 $i$ 个数字为 $u_{i}$，则学籍编号为 $u_{i}$ 的学生的作业纸在排序后位于第 $i$ 位。

如果两位学生提交了相同的作业，应将学籍编号较低的学生作业排在前面。

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

3 4 5 1 2 7 6 8