题目概述

• 时间限制：3s
• 空间限制：1GB

题目描述

终于，我知道了
因为我是这组织的一份子
前面的路
由别的尘群指引着
无垠的空间中我不再迷茫
但心中隐隐的有些失落
“暂且不管，
跟着他们走吧，
这样挺轻松的。”
我对自己说

---

渐渐地，组织关系越来越明确而复杂，也自然出现了领袖，所有尘埃都遵循着他的意志，我们的目标是清楚的，而我们自己又是盲目的。

为了方便管理，领袖依次给每个尘埃编号1..n，再把所有尘埃排成了一横排，这一横排不一定按着1..n的顺序，但肯定是1..n的一个排列。
领袖常常要安排这一横排中的连续一段尘埃[l..r]去做某项工作，他看到这一段尘埃混乱的编号顺序很不满，会要求[l..r]这一段 原地 从小到大或从大到小排序（当然，只是这一段内部，段外的尘埃不参与排序）。
经过多次这样的排序后，领袖想知道最终第k个位置的尘埃的编号是多少？

输入

接下来t组数据。 每组数据中：
第一行有两个整数n,m，其中m表示操作数目。
第二行是空格隔开的n个正整数a[1],a[2],...,a[n]，表示尘埃编号的初始值，保证它是1～n的一个排列。
接下来m行，每行三个整数opt,l,r，表示一次操作：
0 l r: 将[l..r]这一段尘埃从小到大排序。
1 l r: 将[l..r]这一段尘埃从大到小排序。
最后一行为整数k。

输出

输出一行，表示最终第k个位置的尘埃的编号是多少。

样例

输入

6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

输出

5

提示

1 6 2 5 3 4
-> [1 2 5 6] 3 4
-> 1 2 [6 5 4 3]
-> 1 [2 5 6] 4 3
最终a[3]=5

数据范围

\(1<=n,m<=100000\)
\(1<=k<=n\)
\(1<=l<=r<=n\)
\(opt \in \{0,1\}\)

数据分布

1-5 \(n,m<=10000\)
6-10 \(n<=10000,m<=50000\)
11-20 无特殊限制