我妻由乃给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作。

1. 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。
2. 查询区间 $[l,r]$ 内第 $k$ 小值。

输入格式

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

第二行 $n$ 个整数表示序列 $a$。

后面 $m$ 行：

1 l r x y : 把区间 $[l,r]$ 中所有 $x$ 变成 $y$。

2 l r k : 查询区间 $[l,r]$ 中的 $k$ 小值。

输出格式

对于每个询问，输出一个整数表示答案。

样例数据

样例输入

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

样例输出

2
1

子任务

Idea：f321dd，Solution：f321dd&nzhtl1477，Code：nzhtl1477&Claris，Data：nzhtl1477&Juan_feng

$1\le n,m,a_i \le 10^5$。

By f321dd & nzhtl1477 & Claris