/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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