DZY has a sequence $a[1..n]$. It is a permutation of integers $1 \sim n$.
Now he wants to perform two types of operations:
$0 \,\,l \,\,r$: Sort $a[l..r]$ in increasing order.
$1\,\, l \,\,r$: Sort $a[l..r]$ in decreasing order.
After doing all the operations, he will tell you a position $k$, and ask you the value of $a[k]$.
Input
First line contains $t$, denoting the number of testcases.
$t$ testcases follow. For each testcase:
First line contains $n,m$. $m$ is the number of operations.
Second line contains $n$ space-separated integers $a[1],a[2],\cdots,a[n]$, the initial sequence. We ensure that it is a permutation of $1\sim n$.
Then $m$ lines follow. In each line there are three integers $opt,l,r$ to indicate an operation.
Last line contains $k$.
($1\le t \le 50,1\le n,m \le 100000,1\le k \le n, 1\le l\le r\le n, opt \in \{0,1\}$. Sum of $n$ in all testcases does not exceed $150000$. Sum of $m$ in all testcases does not exceed $150000$)
Output
For each testcase, output one line - the value of $a[k]$ after performing all $m$ operations.
