#214516. [JOISC 2016] 回转寿司 / Sushi

在回转寿司店 JOI，寿司被放置在环形传送带上运送。传送带以逆时针方向旋转。当前，店内有从第 1 号到第 号的 位顾客，他们按编号顺序逆时针围坐在传送带周围。第 号顾客的旁边是第 1 号顾客。

每位顾客手持一枚寿司。每枚寿司都有一个称为“价格”的固定数值。顾客离店时，需支付与其所持寿司价格相等的金额。

回转寿司店 JOI 正在实施一项特别的限时促销活动。该活动分为 轮，按顺序从传送带前端提供寿司。第 轮（）提供的寿司内容由三个整数组成 表示。

限时促销的规则如下。在促销开始前，店员将回收传送带上所有的寿司。然后对 依次执行以下步骤 1 至 3：

1. 在传送带前端、第 号顾客的前方位置，放置一枚价格为 的寿司。
2. 寿司从第 号顾客的位置移动至第 号顾客的位置，沿传送带逆时针方向行进。途经的每位顾客将对寿司执行以下操作：
   • 若该寿司的价格小于顾客当前所持寿司的价格，则顾客将自己的寿司与传送带上的寿司交换。
   • 若该寿司的价格大于或等于顾客当前所持寿司的价格，则不进行交换。
3. 寿司经过第 号顾客前方后，店员将回收该寿司。

你是一名在店员手下实习的学徒，负责清洗店内的寿司。为准备清洗工作，你需要提前弄清楚在限时促销的 轮提供中，店员每次回收的寿司价格分别是多少。

补充（比赛结束后追记）

当 时，仅第 号顾客执行第 2 步操作。

题目

给定每位顾客在限时促销开始前各自所持寿司的价格信息，以及限时促销中每轮提供的寿司信息，编写程序求出每轮提供中店员回收的寿司价格。

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

• 第 1 行包含两个整数 和 ，以空格分隔。这表示顾客人数为 ，限时促销中寿司的提供轮数为 。
• 接下来的 行中，第 行（）包含一个整数 。这表示第 号顾客在限时促销开始前持有价格为 的寿司。
• 接下来的 行中，第 行（）包含三个整数 、 和 ，以空格分隔。这表示第 轮提供的寿司由三元组 表示。

输出共 行。第 行（）输出一个整数，表示在第 轮寿司提供中，店员回收的寿司价格。

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

样例 1 解释

第 1 至第 6 号顾客在每轮寿司提供后所持寿司的价格如下：

• 第 1 轮寿司提供后：
• 第 2 轮寿司提供后：
• 第 3 轮寿司提供后：
• 第 4 轮寿司提供后：
• 第 5 轮寿司提供后：
• 第 6 轮寿司提供后：
• 第 7 轮寿司提供后：

数据范围

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

• 。
• 。
• （）。
• （）。
• （）。
• （）。

子任务

子任务 1 [5 分]

满足以下条件：

• 。
• 。

子任务 2 [15 分]

满足以下条件：

• （）。
• （）。

子任务 3 [80 分]

无额外限制。

翻译由 Qwen3-235B 完成