Migrated from Lutece 2524 树魔法

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

UESTC 的集训室门前有一排树，其中第一棵是线段树，第二棵是平衡树，第三棵是动态树……

这些树一共有 $n$ 棵，编号为 $1$ 到 $n$。其中第 $i$ 棵的高度是 $h_i$。

魔法少女 Sugarii 正在练习树魔法。每次使用树魔法，她可以选择一棵树 $i$，使这棵树的高度变为 $x$。

猛男 Fatdog_jo 正在练习修树。每次练习前他都会选择一个区间 $[l, r]$，然后选出区间中第 $k$ 高的树进行修剪。Sugarii 觉得 Fatdog_jo 剪得并不好看，于是当 Fatdog_jo 练习完后，Sugarii 会使用树魔法让这棵树变回修剪之前的样子（即每次修树不会对序列 $h_1, h_2, \ldots, h_n$ 造成影响）。

Fatdog_jo 想请你帮忙记录一下他修过的树在修之前的高度。

Input

输入的第一行包含一个正整数 $T\ (1 \leq T \leq 10^5)$，表示有 $T$ 组测试数据。

每组测试数据的第一行包含两个正整数 $n, m\ (1 \leq n, m \leq 10^5)$，表示这些树一共有 $n$ 棵，Sugarii 使用树魔法和 Fatdog_jo 修树的次数一共为 $m$。

接下来的一行包含 $n$ 个正整数 $h_1, h_2, \ldots, h_n\ (1 \leq h_i \leq 10^9)$，表示最开始每棵树的高度。

接下来的 $m$ 行，每行包含若干正整数，格式是下列两种之一：

• 1 i x 表示 Sugarii 使用树魔法将树 $i\ (1 \leq i \leq n)$ 的高度变为了 $x\ (1 \leq x \leq 10^9)$。
• 2 l r k 表示 Fatdog_jo 将选择修剪区间 $[l, r]\ (1 \leq l \leq r \leq n)$ 中第 $k\ (1 \leq k \leq r - l + 1)$ 高的树。

保证对于所有的 $T$ 组数据，有 $\sum n \leq 10^5, \sum m \leq 10^5$。

Output

设 Fatdog_jo 修树的次数为 $q$，请你输出 $q$ 行，第 $i$ 行的数表示 Fatdog_jo 第 $i$ 次修剪的树在修之前的高度。

Samples

2
3 5
5 3 8
1 3 3
1 2 9
2 1 2 1
1 2 1
2 3 3 1
5 10
1 7 3 9 4
2 5 5 1
2 4 5 2
2 1 2 2
2 5 5 1
1 1 9
2 4 5 2
1 4 2
2 3 3 1
2 1 2 2
2 5 5 1

9
3
4
4
1
4
4
3
7
4

Resources

2021 UESTC ICPC Training for Data Structures