#6708. 盘子摆放

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

题目描述

「为了让顾客第一时间知道我们店的招牌,把所有的盘子按里面菜品价值从大到小的排序一遍」店长命令道

「不行,前面的东西太贵了会显得很不亲民,把第二个盘子到第五个盘子从小到大再排序一遍」

「店长,我觉得这样排序不如刚刚的好看」店员怯怯的说道

「我不要你觉得,我要我觉得,你觉得没有用我觉得有用好吗?」

店长每天都要求店员反反复复的摆放店里的 n 个盘子,每个盘子里都装着价值为 w_i 的菜品,店长的命令要求店员将第 l 个到第 r 个盘子按菜品价值按从小到大或从大到小的顺序重新摆放一遍,店员简直快要疯了,不过所幸,他发现每天店长只会在打烊的时候问他第 k 个盘子的菜品的价值,不过这样让他受够了,他想让你来帮他这个忙。

输入格式

第一行包含三个整数 n,\,m,\,k ,表示盘子的数量、排序的次数和店长打烊时询问的位置。

第二行包含 n 个整数 w_i ,第 i 个整数表示初始时第 i 个盘子里的菜品的价值,保证 w [\,1,\,n\,] 的一个排列。

下面 m 行,每行三个整数 op,\,l,\,r ,表示将第 l 个到第 r 个盘子重新摆放,若 op=0 ,则按照 w_i 从小到大排序,若 op=1 ,则按照 w_i 从大到小排序。

输出格式

输出包含一个整数,表示最后的 w_k

样例

样例输入

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

样例输出

1

数据范围与提示

对于 100\% 的数据,保证 n,m\le10^5