配点 : 400 点
問題文
hiikunZ 你是智力问答比赛的组织者,但你不擅长管理分数。因此,我决定为您编写一个程序来管理“攻击生存”规则中的分数。编写一个程序来解决以下问题。
问答比赛 N 参与者正在参与, 它们的编号最大为 1 减去 N 。每个参与者都有一个参数,称为“体力”。一开始,参与者 i 的体力是 A_i 。和 Q 次, 发生 2 类型的事件。
1 x y: 参加者 x 被授予 正确回答 y 问题。随后,与会人员 x 以外的健康状况 0 所有参与者的健康状况大于 错误回答 y 减少。2 x y: 参加者 x 被授予 正确回答 y 问题。随后,与会人员 x 的体力为 y 减少。
每进行一次活动,您的体力都会在活动前减少。 0 更大了,但活动结束后我的耐力下降了。 0 参与人数如下递增顺序请列举。
制約
- 1 \leq N,Q \leq 200000
- 1 \leq A_i \leq 10^9
- 1 \leq x \leq N
- 1 \leq y \leq 10^9
- 在每个事件发生之前,参与者 x 有体力 这意味着第 0 大于
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。这里 这意味着第 event_i 是 您也可以写 i 个事件。
N Q A_1 A_2 \cdots A_N event_1 event_2 \vdots event_Q
事件以下列格式之一给出。 在第
1 x y
2 x y
出力
Q 行。 在
i 行中,i 次事件之前,健康状况为 0 变大了,但是体力也变大了 0 以下参与者人数及其人数递增顺序请以空格分隔输出。
入力例 1
4 2 5 5 5 10 1 2 5 2 4 5
出力例 1
2 1 3 1 4
最初,每个参与者的体力为 (5,5,5,10) 。
1 第一场比赛结束后,每位参赛者的体力为 (0,5,0,5) 。
1 在第二个活动之前,你的体力将会降低。 0 变大了,但是体力也变大了 0 以下参与者为参与者。 1 和参与者 3 可以得到第 2 人。
2 第一场比赛结束后,每位参赛者的体力为 (0,5,0,0) 。
2 在第二个活动之前,你的体力将会降低。 0 变大了,但是体力也变大了 0 以下参与者为参与者。 4 可以得到第 1 人。
入力例 2
4 3 20 10 5 5 1 2 1 1 2 500 2 2 500
出力例 2
0 3 1 3 4 1 2