该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

大样例在题库第3587题下载

冒泡排序二合一 (sort)

题目描述

给定一个长度为 $n$ 的排列 $a_i$，有两种询问，所有询问相互独立（每次询问后数组复原）：

1. 类型1：给定 $l, r, k, x$，将区间 $[l, r]$ 冒泡排序 $k$ 轮之后，求数字 $x$ 在数组中的下标；
2. 类型2：给定 $l, r, k, x$，将区间 $[l, r]$ 冒泡排序 $k$ 轮之后，求下标 $x$ 位置上的值。

一轮对区间 $[l, r]$ 的冒泡排序定义：依次遍历 $i=l, l+1, \dots, r-1$，若 $a_i>a_{i+1}$，则交换 $a_i$ 与 $a_{i+1}$。

输入格式

在文件 sort.in 中输入。

第一行三个正整数 $n, q, op$：$n$ 为序列长度，$q$ 为询问个数，$op=1$ 代表所有询问都是类型1，$op=2$ 代表所有询问都是类型2； 第二行 $n$ 个正整数，为排列 $a$； 接下来 $q$ 行，每行四个整数 $l\ r\ k\ x$，代表一组询问参数。

输出格式

在文件 sort.out 中输出。

共 $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

样例输出 #1

3
1
2
1

样例输入 #2

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

样例输出 #2

3
1
2
1

数据范围

• $1 \le n,q \le 6 \times 10^5$
• $op \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,\dots,n$ 的一个排列。