在 2016 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。

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

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

注意，这里是对下标在区间 [l,r] 内的数排序。
最后询问第 q 位置上的数字。

输入数据的第一行为两个整数 n 和 m，n 表示序列的长度，m 表示局部排序的次数。

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

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

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

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

河北省选 2016 第一天第二题。

对于 30\% 的数据，n,m\leq 1000；

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