A: Many Kinds of Apples

Problem Statement

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.

* "harvest apples": put d x-th apples into the x-th box.
* "ship apples": take d x-th apples out from the x-th box.



However, not all instructions are possible to carry out. Now we call an instruction which meets either of following conditions "impossible instruction":

* When Mon harvest apples, the amount of apples exceeds the capacity of that box.
* When Mon tries to ship apples, there are not enough apples to ship.



Your task is to detect the instruction which is impossible to carry out.

Input

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".

Constraints

All input values ​​are integers, and satisfy following constraints.

* 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)



Output

If there is "impossible instruction", output the index of the apples which have something to do with the first "impossible instruction".

Otherwise, output 0.

Sample Input 1


2
3 3
Four
1 1 2
one two Three
2 1 3
2 2 3


Sample Output 1


1

In this case, there are not enough apples to ship in the first box.

Sample Input 2


2
3 3
Four
1 1 3
2 1 2
one two Three
1 1 3


Sample Output 2


1

In this case, the amount of apples exceeds the capacity of the first box.

Sample Input 3


3
3 4 5
Four
1 1 3
one two Three
1 3 5
2 2 2


Sample Output 3


0

Sample Input 4


6
28 56 99 3 125 37
Ten
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


Sample Output 4


3





Example

Input

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


Output

1
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }


/*
<url:https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp18Day3/problems/A>
問題文============================================================
 
 林檎農家で働くMonの仕事は「林檎の収穫」と「林檎の出荷」の二つである。
 育てている林檎の種類は N 種あり、収穫した林檎はそれぞれ区別された N 個の箱に保管される。
 出荷は箱に保管されている林檎から行われ、指定された種類の林檎を出荷する。
 林檎は (1≤i≤N) の番号付けによって種類が区別されており、 i 番目の種類の林檎は 箱 i に保管されるものとする。
 各箱 i (1≤i≤N) には最大 ci 個の林檎をいれることができ、初め各箱に入っている林檎の個数は 0 個である。
 
 Monはこれらの仕事を上司であるKukuiの指示に完全に従う。
 指示は全部で Q 回あり、各指示は以下の 2 つのうちのどちらかである。
 
 林檎の収穫 ：箱 x に、収穫した d 個の林檎 x を入れる
 林檎の出荷 ：箱 x から、 d 個の林檎 x を取り出す
 ただし、kukuiの指示は必ずしも理にかなっているとは言えず、理不尽なものが含まれている可能性がある。
 それを判定するプログラムを作ってほしい。 ここで理不尽な指示とは以下の 2 つのことを指す。
 
 林檎の収穫をする際に箱の最大容量を超える
 林檎の出荷をする際に箱の中の林檎が足りなくなる

=================================================================

解説=============================================================

================================================================
*/

int solve(){
    int N; cin >> N;
    vector<int> c(N);
    for(auto& in:c) cin >> in;
    int Q; cin >> Q;
    vector<int> t(Q),x(Q),d(Q);
    vector<int> hako(N,0);
    for(int i = 0; i < Q;i++){
        int t,x,d; cin >> t >> x >> d;
        x--;
        if(t==1){
            hako[x] += d;
            if(hako[x] > c[x]) return x+1;
        }else{
            hako[x] -= d;
            if(hako[x] < 0) return x+1;
        }
    }
    return 0;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}

