排序

【题目描述】

在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要热情活泼可爱自律自信的你来帮助她。

这个难题是这样子的：给出一个 $1$ 到 $n$ 的全排列，现在对这个全排列序列进行 $m$ 次局部排序，排序分为两种：

- $(0,l,r)$ 表示将区间 $[l,r]$ 的数字升序排序

- $(1,l,r)$ 表示将区间 $[l,r]$ 的数字降序排序

最后询问第 $q$ 个位置上的数字。

【输入格式】

输入数据的第一行为两个整数 $n$ 和 $m$，

$n$ 表示序列的长度，$m$ 表示局部排序的次数。

第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个全排列。

接下来输入 $m$ 行，每一行有三个整数 $op,l,r$，$op$ 为 $0$ 代表升序排序，$op$ 为 $1$ 代表降序排序，$l,r$ 表示排序的区间。

最后输入一个整数 $q$，$q$ 表示排序完之后询问的位置，$1≤q≤n$。

【输出格式】

输出数据仅有一行，一个整数，表示按照顺序将全部的局部排序完成后第 $q$ 位置上的数字。

【样例1输入】

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

【样例1输出】

5

【样例2】

点击下载样例2

【数据规模】

对于 $30\%$ 的数据，$1≤n≤100，1≤m≤100$;

对于 $100\%$ 的数据，$1≤n≤10^5，1≤m≤10^5$;