Byterina 老师是东比特郡第 64 小学的一名教师，她最近给学生们布置了以下家庭作业。孩子们需要记录接下来 $n$ 天的温度，并将结果收集起来写成一行。

不幸的是，在作业截止日期的前一天，只有 Alina 认真完成了任务。Alina 的朋友 Kate 请她分享结果。Alina 不情愿地同意了，但她要求 Kate 对结果稍作修改，以免看起来一模一样。于是，Kate 复制了 Alina 的结果，但修改了其中一个数据（Kate 并没有费心去检查她编造的温度是否真的与 Alina 收集的温度不同……）。接着，Wojtek 复制了 Kate 的结果，同样自己修改了其中一个数据。Matthew 复制了 Wojtek 的结果，Martin 复制了 Matthew 的，Lidia 复制了 Martin 的，以此类推。最终，所有学生都有了属于他们自己的结果！

Byterina 老师刚刚收齐了全班的作业。她决定回家批改这些结果，现在她只想先把它们整理好。她希望按字典序排列这些作业——如果作业 $A$ 和作业 $B$ 在最左侧的不同位置上，作业 $A$ 的温度低于作业 $B$ 的温度，则作业 $A$ 应排在作业 $B$ 之前。

Byterina 老师应该按什么顺序排列这些作业？

输入格式

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

第二行包含 $n$ 个整数 $t_1, \dots, t_n$，表示 Alina 记录的连续测量值。我们假设 Alina 的编号为 $1$ ($0 \le t_i \le 10^9$)。

接下来的 $m-1$ 行，每行包含两个整数 $p_i, x_i$ ($1 \le p_i \le n, 0 \le x_i \le 10^9$)；第 $i$ 行表示编号为 $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