题目描述

小D有 $n$ 个积木，每个积木有一个高度，各不相同且都小于等于 $n$ 。

现在小D闲着无聊，想要将 $n$ 个积木排序，但是他觉得将所有积木都排序实在是太无聊了，所以决定采取有趣的部分排序方式，进行 $m$ 次操作，每次操作是以下两种操作的一种。

1.\t将 $[l,r]$ 区间里的积木按照高度从小到大的顺序排序 2.\t将 $[l,r]$ 区间里的积木按照高度从大到小的顺序排序

当然，小D并不想知道所有积木的高度，他只会在最后询问你位置 $q$ 的积木的高度。

输入格式

第一行是两个整数， $n$ 和 $m$

第二行为 $n$ 个整数，表示积木的高度。

接下来 $m$ 行，输入三个整数 $op,l,r$ ，如果 $op=0$ ，则为第一种操作，如果 $op=1$ ，则为第二种操作。

最后输入一个整数 $q$

输出一个整数，表示位置 $q$ 的积木的高度

对于 $30\%$ 的数据， $n,m \le 1000$

对于 $100\%$ 的数据， $n,m \le 10^5$