A：沢山の種類の林檎 (Many Kinds of Apples)

問題

林檎農家で働くMonの仕事は「林檎の収穫」と「林檎の出荷」の二つである。 育てている林檎の種類は N 種あり、収穫した林檎はそれぞれ区別された N 個の箱に保管される。出荷は箱に保管されている林檎から行われ、指定された種類の林檎を出荷する。 林檎は (1 \leq i \leq N) の番号付けによって種類が区別されており、 i 番目の種類の林檎は 箱 i に保管されるものとする。 各箱 i (1 \leq i \leq N) には最大 c_i 個の林檎をいれることができ、初め各箱に入っている林檎の個数は 0 個である。

Monはこれらの仕事を上司であるKukuiの指示に完全に従う。 指示は全部で Q 回あり、各指示は以下の 2 つのうちのどちらかである。

• 林檎の収穫 ：箱 x に、収穫した d 個の林檎 x を入れる
• 林檎の出荷 ：箱 x から、 d 個の林檎 x を取り出す

ただし、kukuiの指示は必ずしも理にかなっているとは言えず、理不尽なものが含まれている可能性がある。 それを判定するプログラムを作ってほしい。 ここで理不尽な指示とは以下の 2 つのことを指す。

• 林檎の収穫をする際に箱の最大容量を超える
• 林檎の出荷をする際に箱の中の林檎が足りなくなる

入力形式

N
c_1 c_2 $\cdots$ c_N
Q
t_1 x_1 d_1
t_2 x_2 d_2
$\vdots$
t_Q x_Q d_Q

1 行目には自然数 N が与えられ、林檎の種類数を表す。

2 行目には c_i (1 \leq i \leq N) が空白区切りで与えられ、i 番目の箱の容量を表す。

3 行目には自然数 Q が与えられ、指示の回数を表す。

引き続く Q 行には t_i x_i d_i (1 \leq i \leq Q) が与えられ、指示の種類、 扱う林檎の番号、 林檎の個数を表す。

t_i が 1 の時「林檎の収穫」を、 t_i が 2 の時「林檎の出荷」を表す。

制約

入力は全て自然数であり以下の制約を満たす。

• 1 \leq N \leq 1,000
• 1 \leq c_i \leq 100,000 (1 \leq i \leq N)
• 1 \leq Q \leq 100,000
• t_i \in \{1, 2\} (1 \leq i \leq Q)
• 1 \leq x_i \leq N (1 \leq i \leq Q)
• 1 \leq d_i \leq 100,000 (1 \leq i \leq Q)

出力形式

理不尽な指示がある場合、最初にされる理不尽な指示の対象となる、林檎の種類の番号を出力せよ。 理不尽な指示が存在しない場合、0 を出力せよ。

入力例1

2
3 3
4
1 1 2
1 2 3
2 1 3
2 2 3

出力例1

1

1 番目の箱の林檎が足りません。

入力例2

2
3 3
4
1 1 3
2 1 2
1 2 3
1 1 3

出力例2

1

1 番目の箱が溢れてしまいます。

入力例3

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

出力例3

0

入力例4

6
28 56 99 3 125 37
10
1 1 10
1 1 14
1 3 90
1 5 10
2 3 38
2 1 5
1 3 92
1 6 18
2 5 9
2 1 4

出力例4

3

Note

Link

 

---