题目描述

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

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

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

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

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