Given a circular sequence ~A~ with ~n~ integers, denoted as ~a_1, a_2, \ldots, a_n~ in clockwise order. Bob is going to perform ~q~ operations. Each operation will give an interval ~[L, R]~ and an integer ~x~. Bob will modify the sequence as follows.

for (int i = L; i <= R; i++) {
    if (a[i] > x) swap(a[i], x);
}

Since the sequence is circular, the given ~R~ may be less than ~L~. Bob will perform the above operation from ~L~ to ~R~ in clockwise order. After each operation, Bob wants to know the value of ~x~. Can you write a program to help him?

Input Specification

The first line of input contains two integers ~n~ and ~q~ (~1 \le n \le 400\,000~, ~1 \le q \le 25\,000~), indicating the length of the sequence and the number of operations.

Each of the following ~n~ lines contains one integer ~a_i~ (~1 \le a_i \le 10^9~), the ~i~-th element in the sequence.

Each of the following ~q~ lines contains three integers ~L~, ~R~, and ~x~ (~1 \le L, R \le n~, ~1 \le x \le 10^9~), indicating an operation.

Output Specification

Output ~q~ lines. Each line contains one integer, the final value of ~x~ after the operation.

Constraints

Subtask	Points	Additional constraints
~1~	~15~	~n \le 2000~, ~q \le 2000~.
~2~	~15~	~L=1~, ~R=N~.
~2~	~70~	No additional constraints.

Sample Input 1

6 7
8
6
7
4
5
9
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3

Sample Output 1

7
9
8
7
8
6
5

Explanation

• The initial sequence is like ~[8, 6, 7, 4, 5, 9]~.
• After the ~1~st operation, it's like ~[8, 5, 6, 4, 5, 9]~ and ~x = 7~.
• After the ~2~nd operation, it's like ~[8, 5, 6, 4, 4, 5]~ and ~x = 9~.
• After the ~3~rd operation, it's like ~[7, 5, 6, 4, 4, 5]~ and ~x = 8~.

Sample Input 2

4 2
5
2
4
7
1 4 3
1 4 1

Sample Output 2

7
5