P14400 [JOISC 2016] 回转寿司 / Sushi

在回转寿司店 JOI，寿司被放置在环形传送带上运送。传送带以逆时针方向旋转。当前，店内有从第 1 号到第 $N$ 号的 $N$ 位顾客，他们按编号顺序逆时针围坐在传送带周围。第 $N$ 号顾客的旁边是第 1 号顾客。 每位顾客手持一枚寿司。每枚寿司都有一个称为“价格”的固定数值。顾客离店时，需支付与其所持寿司价格相等的金额。 回转寿司店 JOI 正在实施一项特别的限时促销活动。该活动分为 $Q$ 轮，按顺序从传送带前端提供寿司。第 $i$ 轮（$1 \le i \le Q$）提供的寿司内容由三个整数组成 $(S_i, T_i, P_i)$ 表示。 限时促销的规则如下。在促销开始前，店员将回收传送带上所有的寿司。然后对 $i = 1, 2, \ldots, Q$ 依次执行以下步骤 1 至 3： 1. 在传送带前端、第 $S_i$ 号顾客的前方位置，放置一枚价格为 $P_i$ 的寿司。 2. 寿司从第 $S_i$ 号顾客的位置移动至第 $T_i$ 号顾客的位置，沿传送带逆时针方向行进。途经的每位顾客将对寿司执行以下操作： - 若该寿司的价格小于顾客当前所持寿司的价格，则顾客将自己的寿司与传送带上的寿司交换。 - 若该寿司的价格大于或等于顾客当前所持寿司的价格，则不进行交换。 3. 寿司经过第 $T_i$ 号顾客前方后，店员将回收该寿司。 你是一名在店员手下实习的学徒，负责清洗店内的寿司。为准备清洗工作，你需要提前弄清楚在限时促销的 $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 解释 第 1 至第 6 号顾客在每轮寿司提供后所持寿司的价格如下： - 第 1 轮寿司提供后：$8, 5, 6, 4, 5, 9$ - 第 2 轮寿司提供后：$8, 5, 6, 4, 4, 5$ - 第 3 轮寿司提供后：$7, 5, 6, 4, 4, 5$ - 第 4 轮寿司提供后：$2, 5, 6, 4, 4, 5$ - 第 5 轮寿司提供后：$2, 5, 6, 4, 4, 5$ - 第 6 轮寿司提供后：$2, 5, 5, 1, 4, 4$ - 第 7 轮寿司提供后：$2, 5, 3, 1, 4, 4$ ### 数据范围 所有输入数据均满足以下条件： - $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 2000$。 - $Q \le 2000$。 **子任务 2 [15 分]** 满足以下条件： - $S_i = 1$（$1 \le i \le Q$）。 - $T_i = N$（$1 \le i \le Q$）。 **子任务 3 [80 分]** 无额外限制。 翻译由 Qwen3-235B 完成