#2055. 「TJOI / HEOI2016」排序

内存限制:256 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

  1. (0, l, r) 表示将区间 [l, r] 的数字升序排序
  2. (1, l ,r) 表示将区间 [l, r] 的数字降序排序

排序后询问第 q 位置上的数字。

输入格式

输入数据的第一行为两个整数 n m n 表示序列的长度, m 表示局部排序的次数 ( 1 \leq n, m \leq 10^5 )。
第二行为 n 个整数,表示 1 n 的一个全排列。
接下来输入 m 行,每一行有三个整数 \text{op}, l, r \text{op} 0 代表升序排序, \text{op} 1 代表降序排序, l, r 表示排序的区间。
最后输入一个整数 q q 表示排序完之后询问的位置, 1 \leq q \leq n

输出格式

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

样例

样例输入

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

样例输出

5