附加文件

题目描述

N 头奶牛排成一排，第 i 头奶牛的身高为 Hi。所有奶牛的身高两两不同，且均为不超过 N 的正整数。

Farmer John 对奶牛发布了 Q 条指令，每条指令形如 k a b，表示将当前队伍区间 [a,b] 中的奶牛按身高重新排队，当 k=0 时按身高升序排队，当 k=1 时按身高降序排队。

所有指令执行结束后，Farmer John 想知道排在第 P 个位置上的奶牛身高是多少？

你能告诉他吗？

输入格式

第一行：包含两个整数 N, Q。

第二行：包含 N 个整数 Hi。

接下来 Q 行：每行包含 3 个整数 k, a, b, 含义如题所述。

最后一行：包含一个整数 P。

输出格式

一个整数，表示答案。

输入样例

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

输出样例

3

数据范围

30% 的数据，$N, Q ≤ 1000$；

100% 的数据，$1 ≤ N, Q ≤ 10^5$，$1 ≤ Hi, P ≤ N$。