题目描述

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

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

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

「我不要你觉得，我要我觉得，你觉得没有用我觉得有用好吗？」

店长每天都要求店员反反复复的摆放店里的 $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$。

样例

input

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

output

1

数据范围与提示

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