Bob has a permutation of positive integers from
to
, denoted as
. He performs
operations on this permutation. Each operation is one of the following types:
0 l r
: Bob will sort all numbers from indexto index
in ascending order.
1 l r
: Bob will sort all numbers from indexto index
in descending order.
After performing all operations, Bob wants to know the number at index
. Write a program to find this number.
Input Specification
The first line contains two integers and
, (
) representing the length of the permutation and the number of operations, respectively.
The second line contains space-separated integers
(
), representing the permutation
.
Each of the next lines contains three integers
,
, and
(
,
) representing an operation type (
or
), left index, and right index, respectively.
The last line contains one integer , (
), the index Bob is interested in.
Output Specification
Output a single integer representing the number at index after performing all
operations.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
No additional constraints |
Sample Input
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
Explanation
- Initially, the permutation is
.
- After the first operation, the permutation becomes
.
- After the second operation, the permutation becomes
.
- After the third operation, the permutation becomes
.
- So, the number at index
is
.
Comments