In 2016, Jiayuan became fond of sequences of numbers. Consequently, she often studies some strange problems regarding sequences, and now she is working on a difficult one that requires your help.

The problem is as follows: Given a permutation of $1$ to $n$, perform $m$ partial sorts on this sequence. The sorting operations are of two types:

• $(0, l, r)$ means to sort the numbers in the interval $[l, r]$ in ascending order.
• $(1, l, r)$ means to sort the numbers in the interval $[l, r]$ in descending order.

Finally, query the number at position $q$.

Input

The first line of the input contains two integers $n$ and $m$, where $n$ is the length of the sequence and $m$ is the number of partial sorts. $1 \le n, m \le 10^5$.

The second line contains $n$ integers, representing a permutation of $1$ to $n$.

The next $m$ lines each contain three integers $op, l, r$, where $op=0$ represents an ascending sort and $op=1$ represents a descending sort, and $l, r$ represent the interval to be sorted.

The last line contains an integer $q$, representing the position to query after all sorting operations are completed, $1 \le q \le n$.

Output

The output consists of a single line containing one integer, which is the number at position $q$ after all partial sorts have been performed in order.

Constraints

For 30% of the data, $1 \le n \le 100$, $1 \le m \le 100$. For 100% of the data, $1 \le n \le 10^5$, $1 \le m \le 10^5$.

Examples

Input 1

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

Output 1

5