Local Sorting Queries

In this problem, you are given a permutation of the integers from 1 to n. You need to perform m local sorting operations on the permutation. Each operation is one of two types:

• 0 l r: Sort the subarray \([l, r]\) in ascending order.
• 1 l r: Sort the subarray \([l, r]\) in descending order.

After performing all operations, output the number at the q-th position of the permutation.

inputFormat

The input consists of several lines:

1. The first line contains three integers \(n\), \(m\), and \(q\) — the size of the permutation, the number of operations, and the query index respectively.
2. The second line contains \(n\) distinct integers representing a permutation of \(\{1, 2, \ldots, n\}\).
3. Each of the next \(m\) lines contains three integers: the operation type and the indices \(l\) and \(r\). An operation of type 0 means sorting the subarray \([l, r]\) in ascending order, whereas type 1 means sorting the subarray \([l, r]\) in descending order. Note that the indices are 1-indexed.

outputFormat

Output a single integer — the number at the \(q\)-th position in the permutation after all operations have been performed.

sample

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

4