Apple Farmer Mon has two kinds of tasks: "harvest apples" and "ship apples".
There are N different species of apples, and N distinguishable boxes. Apples are labeled by the species, and boxes are also labeled, from 1 to N. The i-th species of apples are stored in the i-th box.
For each i, the i-th box can store at most c_i apples, and it is initially empty (no apple exists).
Mon receives Q instructions from his boss Kukui, and Mon completely follows in order. Each instruction is either of two types below.
However, not all instructions are possible to carry out. Now we call an instruction which meets either of following conditions "impossible instruction":
Your task is to detect the instruction which is impossible to carry out.
Input is given in the following format.
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
In line 1, you are given the integer N, which indicates the number of species of apples.
In line 2, given c_i (1 \leq i \leq N) separated by whitespaces. c_i indicates the capacity of the i-th box.
In line 3, given Q, which indicates the number of instructions.
Instructions are given successive Q lines. t_i x_i d_i means what kind of instruction, which apple Mon handles in this instruction, how many apples Mon handles, respectively. If t_i is equal to 1, it means Mon does the task of "harvest apples", else if t_i is equal to 2, it means Mon does the task of "ship apples".
All input values are integers, and satisfy following constraints.
If there is "impossible instruction", output the index of the apples which have something to do with the first "impossible instruction".
Otherwise, output 0.
2 3 3 4 1 1 2 1 2 3 2 1 3 2 2 3
1
In this case, there are not enough apples to ship in the first box.
2 3 3 4 1 1 3 2 1 2 1 2 3 1 1 3
1
In this case, the amount of apples exceeds the capacity of the first box.
3 3 4 5 4 1 1 3 1 2 3 1 3 5 2 2 2
0
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
3