题目背景

自 $2026$ 年起,$fish$有了一个奇怪的习惯,那就是吃虾米时给不同大小的虾米排序。现在$fish$遇到了一点困难，需要你来帮助。

题目描述

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

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

• 1 l r 表示将区间 $[$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

样例输入 #1

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

样例输出 #1

5

提示

对于 $30$ 的数据，$n$,$m$≤$1000$

对于 $100$ 的数据，$n,m\le10^5$，$1$≤$q$≤$n$