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>
                                    #include<iostream>
                                    #include<cstdio>
                                    #include<vector>
                                    #include<queue>
                                    #include<map>
                                    #include<cstring>
                                    #include<string>
                                    #include <math.h>
                                    #include<algorithm>
                                //    #include <boost/multiprecision/cpp_int.hpp>
                                    #include<functional>
                          #define int long long
                                    #define inf  1000000007
                                    #define pa pair<int,int>
                                    #define ll long long
                                    #define pal pair<double,pa>
                                    #define ppa pair<pa,int>
                                    #define ppap pair<int,pa>
                                    #define ssa pair<string,int>
                                    #define  mp make_pair
                                    #define  pb push_back
                                    #define EPS (1e-10)
                                    #define equals(a,b) (fabs((a)-(b))<EPS)
                             
                                    using namespace std;
                          
                                    class Point{
                                    	public:
                                    	double x,y;
                                    	Point(double x=0,double y=0):x(x),y(y) {}
                                    	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
                                    	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
                                    	Point operator * (double a) {return Point(x*a,y*a);}
                                    	Point operator / (double a) {return Point(x/a,y/a);}
                                    	double absv() {return sqrt(norm());}
                                    	double norm() {return x*x+y*y;}
                                    	bool operator < (const Point &p) const{
                                    		return x != p.x ? x<p.x: y<p.y;
                                    	}
                                    	bool operator == (const Point &p) const{
                                    		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
                                    	}
                                    };
                                    typedef Point Vector;
                             
                                    struct Segment{
                                    Point p1,p2;
                                    };
                                     double dot(Vector a,Vector b){
                                    	return a.x*b.x+a.y*b.y;
                                    }
                                    double cross(Vector a,Vector b){
                                    	return a.x*b.y-a.y*b.x;
                                    }
                                    class pa3{
                                        	public:
                                        	int x,y,z;
                                        	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                        	bool operator < (const pa3 &p) const{
                                        		if(x!=p.x) return x<p.x;
                                        		if(y!=p.y) return y<p.y;
                                        		 return z<p.z;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                               				bool operator > (const pa3 &p) const{
                                        		if(x!=p.x) return x>p.x;
                                        		if(y!=p.y) return y>p.y;
                                        		 return z>p.z;
                                        		//return x != p.x ? x<p.x: y<p.y;
                                        	}
                                        	bool operator == (const pa3 &p) const{
                                        		return x==p.x && y==p.y && z==p.z;
                                        	}
                                        		bool operator != (const pa3 &p) const{
                                        			return !( x==p.x && y==p.y && z==p.z);
                                        	}
                                        
                                        };
                                        
                                
        bool parareru(Point a,Point b,Point c,Point d){
        //	if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
        	return abs(cross(a-b,d-c))<EPS;
        }
        double distance_ls_p(Point a, Point b, Point c) {
          if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
          if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
          return abs(cross(b-a, c-a)) / (b-a).absv();
        }
        bool is_intersected_ls(Segment a,Segment b) {
        	if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
        	if(parareru((a.p2),(a.p1),(a.p1),(b.p2))&&parareru((a.p2),(a.p1),(a.p1),(b.p1))){
        //		cout<<"sss"<<endl;
        		if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
        		if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
        		if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
        		if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
        		return false;
        	}
          else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
        }
         
        double segment_dis(Segment a,Segment b){
        	if(is_intersected_ls(a,b))return 0;
        	double r=distance_ls_p(a.p1, a.p2, b.p1);
        	r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
        	r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
        	r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
        	return r;
        }
        Point intersection_ls(Segment a, Segment b) {
          Point ba = b.p2-b.p1;
          double d1 = abs(cross(ba, a.p1-b.p1));
          double d2 = abs(cross(ba, a.p2-b.p1));
          double t = d1 / (d1 + d2);
         
          return a.p1 + (a.p2-a.p1) * t;
        }
         
                        string itos( int i ) {
                        ostringstream s ;
                        s << i ;
                        return s.str() ;
                        }
                         
                        int gcd(int v,int b){
                        	if(v>b) return gcd(b,v);
                        	if(v==b) return b;
                        	if(b%v==0) return v;
                        	return gcd(v,b%v);
                        }
         
                        double distans(double x1,double y1,double x2,double y2){
                        	double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                        	return sqrt(rr);
                        	
                        }
                        /*
        int pr[100010];
        //int inv[100010];
        */ 
        int beki(int wa,int rr,int warukazu){
        	if(rr==0) return 1ll;
        	if(rr==1) return wa%warukazu;
        	if(rr%2==1) return (beki(wa,rr-1,warukazu)*wa)%warukazu;
        	int zx=beki(wa,rr/2,warukazu);
        	return (zx*zx)%warukazu;
        }
          /*
        void gya(){
        	pr[0]=1;
        	for(int i=1;i<100010;i++){
        		pr[i]=(pr[i-1]*i)%inf;
        	}
        	for(int i=0;i<100010;i++) inv[i]=beki(pr[i],inf-2);
        	
        }
         
        */
         //sort(ve.begin(),ve.end(),greater<int>());
                                 //----------------kokomade tenpure------------
        //vector<double> ans(100000000),ans2(100000000);
        /*
        int par[200100],ranks[200100],kosuu[200100];     
         
        void shoki(int n){
        	for(int i=0;i<n;i++){
        		par[i]=i;
        		ranks[i]=0;
        		kosuu[i]=1;
        	}
        }
         
        int root(int x){
        	return par[x]==x ? x : par[x]=root(par[x]);
        }
         
        bool same(int x,int y){
        return root(x)==root(y);
        }
         
        void unite(int x,int y){
         x=root(x);
         y=root(y);
        	int xx=kosuu[x],yy=kosuu[y];
         if(x==y) return;
        	if(ranks[x]<ranks[y]){
        		par[x]=y;
        		kosuu[y]=yy+xx;
        	}
         else {
        	par[y]=x;
        	if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
         	kosuu[x]=yy+xx;
         }
        	return;
        }
*/
int n;
int c[1010];
int s[1010]={0};
        signed main(){
cin>>n;
        	for(int i=1;i<=n;i++)cin>>c[i];
        	
        	int q;
        	cin>>q;
        	for(int fg=1;fg<=q;fg++){
        	int t,x,d;
        		cin>>t>>x>>d;
        		if(t==1){
        		s[x]+=d;
        			if(s[x]>c[x]){
        			cout<<x<<endl;
        				return 0;
        			}
        		}
        		else{
        			s[x]-=d;
        			if(s[x]<0){
        			cout<<x<<endl;
        				return 0;
        			}
        		}
        	
        	}
        	cout<<0<<endl;
        	return 0;
        }
        

