A116131.皓仔的队伍整理

皓仔正在带领同学们进行体能训练。

一共有 $n$ 名同学排成一队，编号为 $1$ 到 $n$。第 $i$ 名同学都有两个属性：

• 身高 $h_i$
• 体重 $w_i$

接下来，皓仔会进行 $m$ 次整理队伍的操作。每次操作都会给出一个区间 $[l,r]$ 和一种排序方式：

• 如果操作类型是 $1$，就把当前队伍中第 $l$ 个到第 $r$ 个位置上的同学，按照体重从小到大排序
• 如果操作类型是 $2$，就把当前队伍中第 $l$ 个到第 $r$ 个位置上的同学，按照身高从小到大排序

如果排序时有两个同学对应属性相同，则编号较小的同学排在前面。

所有操作完成后，请你输出最终队伍中每个位置上的同学编号。

第一行输入两个整数 $n,m$，分别表示同学人数和操作次数。

接下来 $n$ 行，每行输入两个整数 $h_i,w_i$，表示第 $i$ 名同学的身高和体重。

接下来 $m$ 行，每行输入三个整数 $op,l,r$，表示一次操作：

• $op=1$ 表示按照体重排序
• $op=2$ 表示按照身高排序

保证 $1 \le l \le r \le n$。

输出一行，共 $n$ 个整数，表示最终队伍中从前到后每个位置上的同学编号。

【数据范围】

• $1 \le l \le r \le n \le 5000$
• $1 \le m \le 5000$
• $1 \le h_i,w_i \le 10^9$
• $1 \le op \le 2$