题目描述

在 2016 年，佳媛姐姐喜欢上了数字序列。现在他在研究一个难题，需要你来帮助他。
这个难题是这样子的：给出一个 $1$ 到 $n$ 的全排列，现在对这个全排列序列进行 $m$ 次局部排序，排序分为两种：

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

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

输入格式

第一行，输入两个整数 $n$ 和 $m$，表示序列长度和局部排序的次数。
第二行，输入 $n$ 个整数，表示 $1$ 到 $n$ 的一个全排列。
接下来 $m$ 行，每一行三个整数 $op,l,r$，表示一个排序操作。
最后输入一个整数 $q$，表示排序完之后询问的位置。

输出格式

输出共有一行，一个整数，表示按照顺序将全部的部分排序结束后第 $q$ 个位置上的数字。

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

5

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n,m \leq 10^5$，$1 \leq q,l,r \leq n$。