[HEOI2016/TJOI2016]排序

题目描述

在 $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$ 位置上的数字。

输入输出样例

输入样例 #1

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

输出样例 #1

5

说明

河北省选2016第一天第二题。 对于 $30\%$ 的数据,$n,m\leq 1000$ 对于 $100\%$ 的数据,$n,m\leq 10^5$,$1\leq q\leq n$