/* -------------------- ☾ X_WØLF ☕️ ~ code & chill ~ * night vibes * -------------------- Author: Ali Khatibi -------------------- ⣿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢫⣭⣭⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⡘⣀⠉⡛⠿⣿⣿⣿⣿⣿⢀⣿⡟⠹⣧⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣷⠈⣷⣄⠙⣮⡍⠛⠛⠟⢸⣿⠀⠀⢹⣷⠀⠹⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣇⢙⣿⣦⡌⢁⣼⣿⠇⠈⠻⡆⠀⣼⣿⡇⠀⢧⡙⢿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⡎⡿⣫⣴⣿⠟⠁⣼⣿⣶⣅⣼⣿⣿⣿⣧⢸⣿⣦⢙⢿⣿⣿⣿⣿⣿ ⣿⣿⣿⣿⠰⣡⡆⡟⣴⣶⣾⣿⢿⣿⣿⣿⣿⣿⣿⣆⢻⣿⣿⡃⠙⠿⣿⣿⣿ ⣿⣿⣿⡗⢰⣿⢡⡇⢫⡯⢹⣿⣷⣍⠛⣿⣿⣿⣿⣿⡆⢻⣿⣿⣆⠀⣬⣿⣿ ⣿⣿⣿⡧⠈⠛⣸⡇⣾⡭⢉⣙⢉⡛⢷⣮⣿⣿⣿⣿⣧⢸⣿⣿⣿⡇⢻⣿⣷ ⣿⣿⣿⣧⠀⣰⣿⣿⠌⣠⣤⣴⣿⣿⠀⣬⣉⡛⣿⣿⣿⣦⣿⣿⣿⣷⢺⣿⣿ ⣿⣿⣿⢟⣼⣿⣿⡿⢌⣋⠻⠊⢹⡉⠀⢻⣿⠇⣿⣿⣿⣿⢿⣿⣿⣿⢸⣿⣿ ⣿⣿⢫⡾⢻⣿⣿⣾⣿⣿⣿⣿⣿⣷⣤⣄⡍⠀⣿⣿⣿⣿⣹⣿⣿⡿⣼⣿⣿ ⠟⣵⢟⠀⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣫⡀⢸⣿⣿⣿⡏⣿⣿⣿⡇⣾⣿⣿ ⡈⠁⠀⢀⣾⣿⣿⣿⣿⢟⣱⠿⢋⣰⣾⣿⣿⣸⣿⣿⡿⢳⣿⣿⣿⣿⣿⣿⣿ ⣿⣦⣀⠾⠿⠿⠛⠋⣡⣥⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⢧⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣿⣶⣦⠰⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣿⣿⣿⡆⢙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⣿⣿⣿⣿⣿⣿⣇⢨⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ */ #include <bits/stdc++.h> using namespace std; using pii = pair<long long , long long>; #define int long long #define pb push_back #define pp pop_back #define endl '\n' #define all(x) (x).begin(), (x).end() #define wall() cerr << "------------------------------" << '\n' const int llinf = 1e18; const int inf = 1e9; const int maxn = 3e5 + 100; const int MOD = 1e9 + 7; const int SQ = 550; struct query { int l , r , x , id; }; int a[maxn] , p[maxn] , cur[maxn] , ans[maxn]; vector<query> q(maxn , {0 , 0 , 0 , 0}); vector<int> v[maxn]; set<int> nt; int getGrp(int x){ return (x + SQ - 1) / SQ; } int grpBeg(int grp){ return (grp - 1) * SQ + 1; } int grpEnd(int grp){ return grp * SQ; } void solve(){ int n , m; cin >> n >> m; for(int i = 1 ; i <= m ; i++){ cin >> a[i]; v[a[i]].pb(i); } for(int i = 1 ; i <= n ; i++){ cin >> p[i]; nt.insert(i); } int k; cin >> k; for(int i = 1 ; i <= k ; i++){ cin >> q[i].l >> q[i].r >> q[i].x; q[i].id = i; } for(int gp = 1 ; gp <= getGrp(k) ; gp++){ int start = grpBeg(gp); int end = grpEnd(gp); vector<int> cnt(n + 2 , 0ll); vector<int> diff(m + 3 , 0ll); for(int i = 1 ; i <= n ; i++) cnt[i] = cur[i]; for(int i = start ; i <= min(k , end) ; i++){ int L = q[i].l; int R = q[i].r; if(L > R){ diff[L] += q[i].x; diff[1] += q[i].x; diff[R + 1] -= q[i].x; } else{ diff[L] += q[i].x; diff[R + 1] -= q[i].x; } } for(int i = 1 ; i <= m ; i++){ diff[i] += diff[i - 1]; cnt[a[i]] += diff[i]; } auto it = nt.begin(); while(it != nt.end()){ int sec = *it; if(cnt[sec] >= p[sec]){ bool done = false; for(int i = start ; i <= min(k , end) ; i++){ int L = q[i].l; int R = q[i].r; if(L <= R){ for(int pl : v[sec]){ if(L <= pl && pl <= R) cur[sec] += q[i].x; } } else{ for(int pl : v[sec]){ if(L <= pl && pl <= m) cur[sec] += q[i].x; if(1 <= pl && pl <= R) cur[sec] += q[i].x; } } if(cur[sec] >= p[sec]){ ans[sec] = q[i].id; done = true; break; } } if(done){ it = nt.erase(it); continue; } it++; } else it++; } for(int sec : nt){ cur[sec] = cnt[sec]; } } for(int i = 1 ; i <= n ; i++){ if(ans[i] > 0) cout << ans[i] << endl; else cout << "NIE" << endl; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int t = 1; // cin >> t; while (t--) solve(); }