Description

In 2016, sister Jiayuan became fond of number sequences. She often studies various quirky problems about sequences, and now she is working on a hard one that needs your help.

The problem is as follows: given a permutation of $1$ to $n$, perform $m$ local sorts on this sequence. There are two types of sorts:

• 0 l r means sorting the numbers in the interval $[l,r]$ in ascending order.
• 1 l r means sorting the numbers in the interval $[l,r]$ in descending order.

Note that this sorts the numbers whose indices lie in the interval $[l,r]$.
Finally, query the number at position $q$.

Input Format

The first line contains two integers $n$ and $m$, where $n$ is the length of the sequence and $m$ is the number of local sorts.

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

The next $m$ lines each contain three integers $\text{op}, l, r$, where $\text{op}$ being $0$ means ascending sort, $\text{op}$ being $1$ means descending sort, and $l, r$ specify the interval to sort.

Finally, an integer $q$ is given, indicating the position to query after all sorts are finished.

Output Format

Output a single line containing one integer, the number at position $q$ after performing all local sorts in order.

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

5

Hint

Hebei NOI Qualifier 2016 Day 1 Problem 2.

For $30\%$ of the testdata, $n, m \leq 1000$.

For $100\%$ of the testdata, $n, m \leq 10^5$, $1 \leq q \leq n$.

Translated by ChatGPT 5