旋转寿司店 JOI 使用环状传送带运送寿司盘。传送带逆时针旋转。目前，店内有 $N$ 位顾客，编号为 1 到 $N$，他们按编号顺序沿逆时针方向排列在传送带周围。顾客 $N$ 的旁边坐着顾客 1。

每位顾客手中各持有一个盘子。每个盘子都有一个被称为“价格”的数值。在离开店铺时，顾客需要支付与其手中盘子价格相等的金额。

旋转寿司店 JOI 正在进行一场别开生面的限时促销活动。在这次活动中，厨师会分 $Q$ 次依次提供寿司盘。第 $i$ 次 ($1 \le i \le Q$) 提供的盘子信息由三个整数组成的元组 $(S_i, T_i, P_i)$ 表示。

限时促销的规则如下。在促销开始前，厨师会收回传送带上的所有盘子。对于 $i = 1, 2, \dots, Q$，重复执行以下 1 到 3 步：

1. 厨师将价格为 $P_i$ 的盘子放置在传送带上顾客 $S_i$ 面前的位置。
2. 盘子从顾客 $S_i$ 的位置移动到顾客 $T_i$ 的位置。每位经过的顾客会对面前的盘子执行以下操作：
   • 如果该盘子的价格小于自己手中盘子的价格，则将自己的盘子与传送带上的盘子进行交换。
   • 如果该盘子的价格大于或等于自己手中盘子的价格，则不进行交换。
3. 盘子经过顾客 $T_i$ 面前后，厨师将其收回。

你是厨师门下的学徒，负责店里的洗碗工作。由于旋转寿司店 JOI 的盘子根据价格不同，清洗方法也不同，为了准备洗碗工作，你需要预先知道在 $Q$ 次提供中，厨师每次收回的盘子价格是多少。

说明 (竞赛结束后补充)

当 $S_i = T_i$ 时，仅顾客 $S_i$ 执行第 2 步操作。

题目

给定每位顾客在限时促销前持有的盘子信息，以及限时促销中盘子提供的信息，请编写一个程序，求出每次提供盘子时厨师收回的盘子价格。

输入格式

从标准输入读取以下数据：

• 第 1 行包含两个整数 $N, Q$，以空格分隔。这表示顾客人数为 $N$，限时促销中提供盘子的次数为 $Q$。
• 接下来的 $N$ 行中的第 $i$ 行 ($1 \le i \le N$) 包含一个整数 $X_i$。这表示顾客 $i$ 在限时促销前持有价格为 $X_i$ 的盘子。
• 接下来的 $Q$ 行中的第 $i$ 行 ($1 \le i \le Q$) 包含三个整数 $S_i, T_i, P_i$，以空格分隔。这表示第 $i$ 次提供的盘子由元组 $(S_i, T_i, P_i)$ 表示。

输出格式

输出包含 $Q$ 行。标准输出的第 $i$ 行 ($1 \le i \le Q$) 应输出一个整数，表示第 $i$ 次提供盘子时厨师收回的盘子价格。

数据范围

所有输入数据满足以下条件：

• $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$)

子任务

子任务 1 [5 分]

满足以下条件： $N \le 2\,000$ $Q \le 2\,000$

子任务 2 [15 分]

满足以下条件： $S_i = 1$ ($1 \le i \le Q$) $T_i = N$ ($1 \le i \le Q$)

子任务 3 [80 分]

没有额外限制。

样例

输入 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

输出 1

7
9
8
7
8
6
5

输入 2

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

输出 2

7
5

输入 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

输出 3

19
10
14
17
8
10
3
12
7
9