Given a circular sequence $A$ with $n$ integers, denoted as $a_1,a_2,\dots ,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 400000$, $1\le q\le 25000$), 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