At the conveyor-belt sushi restaurant JOI, sushi plates are transported on a circular conveyor belt. The conveyor belt rotates counter-clockwise. Currently, there are $N$ customers in the restaurant, numbered from 1 to $N$, who are seated in order around the conveyor belt in the counter-clockwise direction. Customer 1 is seated next to customer $N$.

Each customer holds exactly one plate. Each plate has a value called its price, and when leaving the restaurant, each customer pays an amount equal to the price of the plate they are holding.

The sushi restaurant JOI is holding a unique time sale. In this time sale, plates are served by the chef in $Q$ separate turns. The content of the $i$-th plate service ($1 \le i \le Q$) is represented by a triplet of integers $(S_i, T_i, P_i)$.

The rules of the time sale are as follows. Immediately before the time sale begins, the chef collects all plates currently on the conveyor belt. Then, the following steps 1 to 3 are repeated for $i = 1, 2, \dots, Q$:

1. The chef places a plate with price $P_i$ at the position in front of customer $S_i$ on the conveyor belt.
2. The plate moves along the conveyor belt from the position of customer $S_i$ to the position of customer $T_i$. Each customer performs the following action regarding the plate currently in front of them:
   • If the price of that plate is smaller than the price of the plate they are currently holding, they exchange their plate with the plate on the conveyor belt.
   • If the price of that plate is greater than or equal to the price of the plate they are currently holding, no exchange is performed.
3. After the plate passes in front of customer $T_i$, the chef collects that plate.

You are an apprentice training under the chef and have been tasked with washing the dishes. At the sushi restaurant JOI, the method for washing plates depends on their price. To prepare for dishwashing, you want to know in advance the price of the plate that the chef will collect after each of the $Q$ services during the time sale.

Note

If $S_i = T_i$, only customer $S_i$ performs the second action.

Input

Read the following data from standard input:

• The first line contains two integers $N$ and $Q$, separated by a space. This indicates that there are $N$ customers and the plates are served $Q$ times during the time sale.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains an integer $X_i$. This indicates that customer $i$ holds a plate with price $X_i$ immediately before the time sale.
• The $i$-th line of the following $Q$ lines ($1 \le i \le Q$) contains three integers $S_i, T_i, P_i$, separated by spaces. This indicates that the $i$-th plate service is represented by the triplet $(S_i, T_i, P_i)$.

Output

The output should consist of $Q$ lines. The $i$-th line of standard output ($1 \le i \le Q$) should contain an integer representing the price of the plate collected by the chef in the $i$-th service.

Constraints

All input data satisfies the following conditions:

• $1 \le N \le 400\,000$
• $1 \le Q \le 25\,000$
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le S_i \le N$ ($1 \le i \le Q$)
• $1 \le T_i \le N$ ($1 \le i \le Q$)
• $1 \le P_i \le 1\,000\,000\,000$ ($1 \le i \le Q$)

Subtasks

Subtask 1 [5 points]

• $N \le 2\,000$
• $Q \le 2\,000$

Subtask 2 [15 points]

• $S_i = 1$ ($1 \le i \le Q$)
• $T_i = N$ ($1 \le i \le Q$)

Subtask 3 [80 points]

• No additional constraints.

Examples

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

Output 1

7
9
8
7
8
6
5

Input 2

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

Output 2

7
5

Input 3

10 10
19
5
8
17
14
3
9
10
7
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3

Output 3

19
10
14
17
8
10
3
12
7
9