在今年，小明的姐姐喜欢上了数字序列。所以她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。 这个难题是这样的：给出一个排列，这个序列有n个数，现在对这个排列序列进行m次局部排序的操作，排序分为两种： 0 l r表示将区间的数字升序排序; 1 l r表示将区间的数字降序排序; 注意，这里是对下标在区间[l,r]内的数排序。 m次操作后，最后询问第q位置上的数字。

输入数据的第一行为两个整数n和m，n表示序列的长度，m表示局部排序的次数。 第二行为n个整数，表示排列的具体数值。 接下来输入m行，每一行有三个整数op,l,r,op为0代表升序排序，op为1代表降序排序，l,r表示排序的区间。 最后输入一个整数q，表示排序完之后询问的位置。

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 q 位置上的数字。

对于样例1： 初始序列为[1,6,2,5,3,4]。 op=0，对[1,4]区间进行升序后，序列为[1,2,5,6,3,4]; op=1，对[3,6]区间进行降序后，序列为[1,2,6,5,4,3]； op=0，对[3,4]区间进行升序后，序列为[1,2,5,6,4,3]； 最后查询第三个位置的数为：5 。

n,m \leq \gdef\foo#1{#1^5} \foo{10}

1 \leq q \leq n

云南编程挑战赛