题目背景

译自 PA 2017 R3T2。

TL=5~10s，ML=512MB。

「你抄就抄吧，但是稍微改改，别和我的一模一样就行。」

题目描述

有 $m$ 个长度为 $n$ 的非负整数序列。第 $i$ 个序列的第 $j$ 项为 $a_{i,j}$。

给定 $a_{1,1},a_{1,2},\cdots,a_{1,n}$。

对于 $2\le i\le m$，给定 $p_i,x_i$，表示：

• $\forall 1\le j\le n$ 满足 $j\neq p_i$，有 $a_{i,j}=a_{i-1,j}$；
• $a_{i,p_i}=x_i$。

将这 $m$ 个序列以字典序为第一关键字，编号为第二关键字排序，输出排序后的序列编号。

输入格式

第一行，两个正整数 $n,m$。

第二行，$n$ 个非负整数 $a_{1,1},a_{1,2},\cdots,a_{1,n}$。

接下来 $(m-1)$ 行，第 $i$ 行两个整数 $p_{i+1},x_{i+1}$。

输出格式

输出一行 $m$ 个正整数，第 $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

提示

• $1\le n\le 5\times 10^5$；
• $2\le m\le 5\times 10^5$；
• $0\le a_{1,i},x_i\le 10^9$；
• $1\le p_i\le n$。