Yuno 在一场比赛中失利，被迫穿上 JK 制服。Claris 赢得了比赛，于是她为 Yuno 买了一些 JK 制服。每件制服都有一个价格。因为 Claris 很有钱，她买了 $n$ 件制服，并将它们放入一个数组 $a_1, a_2, \dots, a_n$ 中。

因为 Yuno 热爱数据结构，她发明了两种操作：

• “1 $l$ $r$ $x$ $y$”：对于 $a_l, a_{l+1}, \dots, a_r$ 中的所有制服，如果某件制服的价格为 $x$，将其价格改为 $y$。
• “2 $l$ $r$ $k$”：Yuno 想穿 $a_l, a_{l+1}, \dots, a_r$ 中价格第 $k$ 低的制服，请告诉她这件制服的价格。

输入格式

第一行包含两个整数 $n$ 和 $m$：制服的数量和操作的数量（$1 \le n, m \le 10^5$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$：制服的价格（$1 \le a_i \le n$）。接下来的 $m$ 行，每行描述一个操作。如果是修改操作，格式为 “1 $l$ $r$ $x$ $y$”，其中 $1 \le l \le r \le n$ 且 $1 \le x, y \le n$。如果是查询操作，格式为 “2 $l$ $r$ $k$”，其中 $1 \le l \le r \le n$ 且 $1 \le k \le r - l + 1$。

输出格式

对于每个查询，输出一行，包含一个整数：查询的答案。

样例

样例输入 1

3 3
2 3 3
2 1 3 1
1 1 3 3 1
2 1 3 2

样例输出 1

2
1