题面

在摆烂了半年之后，小 ∆ 退化为了普及组选手，于是只能出一些普及组的题目，比如冒泡排序。他很好奇一个序列冒泡排序 $k$ 轮之后的样子。具体来讲，给定一个长度为 $n$ 的排列 $a_i$，他有两种询问：

1. 给定 $l, r, k, x$ ，求将 $a_i$ 的区间 $[l, r]$ 冒泡排序 $k$ 轮之后，$x$ 这个数在 数组中的下标；

2. 给定 $l, r, k, x$ ，求将 $a_i$ 的区间 $[l, r]$ 冒泡排序 $k$ 轮之后，$a_x$ 的值。

小 ∆ 在每次询问后都会将序列复原。也就是说询问相互独立。

定义对 ai 的区间 $[l, r]$ 进行一轮冒泡排序为依次对于 $i = l, l+ 1, \cdots , r−1$，若 $a_i$ > $a_{i+1}$，则交换 $a_i, a_{i+1}$

输入格式

第一行，三个正整数 $n, q, o$，其中 $q$ 为询问的个数；$o$ 代表询问的种类，$o = 1, 2$ 分别代表小 ∆ 的询问全是第一、二种的。

第二行，$n$ 个正整数，$a_i$

接下来 $q$ 行，每行四个非负整数 $l, r, k, x$，代表一组询问。

输出格式

$q$ 行，每行一个正整数，对应询问的答案。

样例 1

输入

4 4 1
3 4 2 1
1 4 2 3
1 4 2 2
1 3 1 2
2 4 1 3

输出

3
1
2
1

样例解释

区间 $[1, 4]$ 进行两轮冒泡排序之后，序列变为 $2, 1, 3, 4$

区间 $[1, 3]$ 进行一轮冒泡排序之后，序列变为 $3, 2, 4, 1$

区间 $[2, 4]$ 进行一轮冒泡排序之后，序列变为 $3, 2, 1, 4$

样例 2

输入

4 4 2
3 4 2 1
1 4 2 3
1 4 2 2
1 3 1 2
2 4 1 3

输出

3
1
2
1

样例 3

见下发文件，此样例满足子任务 $1$ 的限制。

样例 4

见下发文件，此样例满足子任务 $1$ 的限制。

样例 5

见下发文件，此样例满足子任务 $4$ 的限制。

样例 6

见下发文件，此样例满足子任务 $5$ 的限制。

数据范围与限制

对于所有数据 $1\le n,q\le 6\times10^5,o\in\{1,2\},1\le l\le r\le n,1\le x\le n,0\le k\le n-1$，保证 $a_i$ 是 $1, 2, \cdots , n$ 的一个排列。

子任务如下：