Sushi (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

At the JOI conveyor belt sushi restaurant, sushi plates are delivered on a circular conveyor belt rotating counterclockwise. There are N customers, numbered 1 to N, seated counterclockwise in this order around the belt. Customer N is next to customer 1.

Each customer initially has one sushi plate. Each plate has a value called its price.

The restaurant holds a special time sale during which Q plates are served one by one. The i-th serving is described by a triple of integers (Si, Ti, Pi):

1. The chef places a plate with price Pi in front of customer Si on the conveyor belt.
2. The plate moves counterclockwise from customer Si to customer Ti. As the plate passes in front of each customer along the way:
   • If the plate has a lower price than the customer's current plate, they swap their plate with the moving one.
   • If not, the customer does nothing.
3. After passing customer Ti, the chef retrieves the plate on the conveyor belt.

Note: In the case that Si = Ti, customer Si is the only one who performs Step (2).

You are in charge of washing plates at the restaurant. As plates are washed differently depending on their price, you want to know in advance the price of the plate retrieved by the chef after each serving.

Task

Given the initial plates of each customer and the Q servings of the time sale, write a program to determine the price of the plate retrieved by the chef after each serving.

Input

• The first line contains two integers N and Q – number of customers and number of servings.
• The next N lines each contain an integer Xi – the initial plate price of customer i.
• The next Q lines each contain three integers Si, Ti, Pi – describing each time sale plate.

Output

Print Q lines. The i-th line contains the price of the plate retrieved after the i-th serving.

Constraints

• 1 ≤ N ≤ 400,000
• 1 ≤ Q ≤ 25,000
• 1 ≤ Xi ≤ 1,000,000,000
• 1 ≤ Si, Ti ≤ N
• 1 ≤ Pi ≤ 1,000,000,000

Subtasks

• Subtask 1 [5 points]: N ≤ 2,000, Q ≤ 2,000
• Subtask 2 [15 points]: For all i, Si = 1 and Ti = N
• Subtask 3 [80 points]: 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

Sample Input 2

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

Sample Output 2

7
5

Sample 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

Sample Output 3

19
10
14
17
8
10
3
12
7
9