题目描述

小杨有 $n$ 张卡片，从左到右编号为 $1$ 到 $n$，第 $i$ 张卡片的数值为 $a_i$。之后他进行了 $q$ 次整理操作，每次选择一个连续区间 $[l,r]$：若操作类型为 $0$，则将该区间内的卡片按数值从小到大排列；若操作类型为 $1$，则将该区间内的卡片按数值从大到小排列。若两张卡片数值相同，无论升序还是降序，编号较小的卡片都排在前面。请输出所有操作完成后卡片编号的顺序以及对应的数值顺序。

输入格式

第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行包含三个整数 $l$、$r$、op，表示一次整理操作。其中 op=0 表示升序整理，op=1 表示降序整理。

输出格式

输出两行。第一行输出最终从左到右的卡片编号；第二行输出最终从左到右的卡片数值。每行相邻两个数之间用一个空格分隔，行末不要输出多余空格。

样例

5 3
4 2 4 1 3
1 5 0
2 4 1
3 5 0

4 1 2 5 3
1 4 2 3 4

样例解释

第一次将全部卡片按数值升序排列，得到编号 4 2 5 1 3；第二次整理第 $2$ 到第 $4$ 张，得到 4 1 5 2 3；第三次整理第 $3$ 到第 $5$ 张，最终得到编号 4 1 2 5 3。

数据范围

$1 \le n \le 1000$，$0 \le q \le 100$，$1 \le a_i \le 10^9$，$1 \le l \le r \le n$，op 只能为 $0$ 或 $1$。