/* Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528) */ #include <bits/stdc++.h> using namespace std; #define int long long #define ull unsigned long long #define ld long double #define pii pair<int, int> #define fi first #define se second #define __builtin_popcount __builtin_popcountll #define all(x) (x).begin(), (x).end() #define BIT(x, i) (((x) >> (i)) & 1) #define MASK(x) ((1ll << (x))) #define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n'; struct FenwickTree { int n; vector<int> fen; FenwickTree(int _n) : n(_n), fen(n + 5, 0) {} void reset() {fill(all(fen), 0);} void update(int idx, int v) { for (int i = idx; i <= n; i += i & -i) fen[i] += v; } int get(int idx) { int sum = 0; for (int i = idx; i; i -= i & -i) sum += fen[i]; return sum; } void updateRange(int l, int r, int v) { update(l, v); update(r + 1, -v); } }; struct Query { int l, r, inc; }; const int MAXN = 3e5 + 5; int n, m, q, owner[MAXN], p[MAXN]; vector<int> pos[MAXN]; Query queries[MAXN]; void init() { cin >> n >> m; for (int i = 1; i <= m; ++i) cin >> owner[i]; for (int i = 1; i <= m; ++i) pos[owner[i]].push_back(i); for (int i = 1; i <= n; ++i) cin >> p[i]; cin >> q; for (int i = 1; i <= q; ++i) { int l, r, inc; cin >> l >> r >> inc; queries[i] = {l, r, inc}; } } // Parallel binary search int l[MAXN], r[MAXN], ans[MAXN]; vector<int> checkset[MAXN]; void solve() { fill(l + 1, l + n + 1, 0); fill(r + 1, r + n + 1, q); fill(ans + 1, ans + n + 1, q + 1); FenwickTree fen(m); while (true) { bool any = 0; for (int i = 1; i <= n; ++i) { if (l[i] <= r[i]) { int mid = (l[i] + r[i]) >> 1; checkset[mid].push_back(i); any = 1; } } if (!any) break; fen.reset(); for (int mid = 0; mid <= q; ++mid) { if (mid) { int u = queries[mid].l; int v = queries[mid].r; int x = queries[mid].inc; if (u <= v) fen.updateRange(u, v, x); else { fen.updateRange(u, m, x); fen.updateRange(1, v, x); } } for (auto o : checkset[mid]) { int sum = 0; for (auto idx : pos[o]) { sum += fen.get(idx); if (sum >= p[o]) break; } if (sum >= p[o]) { r[o] = mid - 1; ans[o] = mid; } else l[o] = mid + 1; } } // Reset for (int i = 0; i <= q; ++i) checkset[i].clear(); } for (int i = 1; i <= n; ++i) if (ans[i] == q + 1) cout << "NIE\n"; else cout << ans[i] << '\n'; } signed main() { #ifdef NCTHANH freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); init(); solve(); return 0; }