Bob has a permutation ~A~ of positive integers from ~1~ to ~n~, denoted as ~a_1, a_2, ..., a_n~. He performs ~m~ operations on this permutation. Each operation is one of the following types:

• 0 l r: Bob will sort all numbers from index ~l~ to index ~r~ in ascending order.
• 1 l r: Bob will sort all numbers from index ~l~ to index ~r~ in descending order.

After performing all ~m~ operations, Bob wants to know the number at index ~p~. Write a program to find this number.

Input Specification

The first line contains two integers ~n~ and ~m~, (~1 \leq n, m \leq 10^5~) representing the length of the permutation and the number of operations, respectively.

The second line contains ~n~ space-separated integers ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq n~), representing the permutation ~A~.

Each of the next ~m~ lines contains three integers ~t_i~, ~l_i~, and ~r_i~ (~0 \leq t_i \leq 1~, ~1 \leq l_i \leq r_i \leq n~) representing an operation type (~0~ or ~1~), left index, and right index, respectively.

The last line contains one integer ~p~, (~1 \le p \le n~), the index Bob is interested in.

Output Specification

Output a single integer representing the number at index ~p~ after performing all ~m~ operations.

Constraints

Subtask	Points	Additional constraints
~1~	~30~	~n \le 100~, ~m \le 100~
~2~	~70~	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 ~[1, 6, 2, 5, 3, 4]~.
• After the first operation, the permutation becomes ~[1, 2, 5, 6, 3, 4]~.
• After the second operation, the permutation becomes ~[1, 2, 6, 5, 4, 3]~.
• After the third operation, the permutation becomes ~[1, 2, 5, 6, 4, 3]~.
• So, the number at index ~3~ is ~5~.