#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
const int OO = (int)1e18;
int numStates, numSectors;
vector<int> sectorState; // sectorState[sector] = state
vector<vector<int>> stateSectors; // stateSectors[state] = {sectors}
vector<int> stateNeed; // stateNeed[state] = sum
int Q;
struct Node {
int sum = 0;
int childL = OO, childR = OO;
int interL, interR;
bool includes (int iSector) {
return (interL <= iSector && iSector <= interR);
}
};
struct SegPers {
int numleaves;
vector<Node> nodes;
vector<int> iRoot; // iRoot[time] = idx of root
SegPers (int n) {
numleaves = 1;
while (numleaves < n) numleaves *= 2;
nodes.resize(2*numleaves-1);
nodes[0].interL = 0, nodes[0].interR = numleaves-1;
for (int i = 0; i < (int)nodes.size(); i++) {
nodes[i].childL = 2*(i+1) - 1;
nodes[i].childR = 2*(i+1);
if (2*(i+1) < (int)nodes.size()) {
int childL = nodes[i].childL, childR = nodes[i].childR;
int mid = (nodes[i].interL + nodes[i].interR) / 2;
nodes[childL].interL = nodes[i].interL;
nodes[childL].interR = mid;
nodes[childR].interL = mid+1;
nodes[childR].interR = nodes[i].interR;
}
}
for (int i = 0; i < (int)nodes.size(); i++) {
if (nodes[i].interL == nodes[i].interR) {
nodes[i].childL = OO;
nodes[i].childR = OO;
}
}
iRoot.emplace_back(0);
// cerr << "SEGTREE INIT:\n";
// for (int i = 0; i < (int)nodes.size(); i++) cerr << nodes[i].interL << " " << nodes[i].interR << "\n";
// cerr << "------------------------\n";
}
void increment (Node node, int idx, int val) {
bool changeL = false, changeR = false;
if (node.childL < (int)nodes.size() && nodes[node.childL].includes(idx)) {
increment(nodes[node.childL], idx, val);
changeL = true;
}
else if (node.childR < (int)nodes.size() && nodes[node.childR].includes(idx)) {
increment(nodes[node.childR], idx, val);
changeR = true;
}
nodes.emplace_back(Node{
node.sum + val,
(changeL ? (int)nodes.size()-1 : node.childL),
(changeR ? (int)nodes.size()-1 : node.childR),
node.interL,
node.interR
});
// cerr << "[" << node.interL << ", " << node.interR << "]: " << node.sum + val << "\n";
}
void increment (int idx, int val) {
increment(nodes[iRoot.back()], idx, val);
iRoot.emplace_back((int)nodes.size() - 1);
}
int query (int qL, int qR, int time) {
Node node = nodes[iRoot[time]];
return query(node, qL, qR);
}
int query (Node node, int qL, int qR) {
int nL = node.interL, nR = node.interR;
if (qL <= nL && nR <= qR) {
return node.sum;
}
else if (qR < nL || nR < qL) {
return 0;
}
else {
return query(nodes[node.childL], qL, qR) + query(nodes[node.childR], qL, qR);
}
}
};
signed main() {
fastIO();
cin >> numStates >> numSectors;
sectorState.resize(numSectors);
stateSectors.resize(numStates);
stateNeed.resize(numStates);
for (int iSector = 0; iSector < numSectors; iSector++) {
cin >> sectorState[iSector];
sectorState[iSector]--;
stateSectors[sectorState[iSector]].emplace_back(iSector);
}
for (int iState = 0; iState < numStates; iState++) {
cin >> stateNeed[iState];
}
cin >> Q;
SegPers segtree(numSectors+1);
for (int iQuery = 0; iQuery < Q; iQuery++) {
int l, r, cnt;
cin >> l >> r >> cnt;
l--, r--;
if (l <= r) {
segtree.increment(l, cnt);
segtree.increment(r+1, -cnt);
segtree.increment(0, 0);
segtree.increment(0, 0);
}
else {
assert(l > r);
segtree.increment(0, cnt);
segtree.increment(r+1, -cnt);
segtree.increment(l, cnt);
segtree.increment(numSectors, -cnt);
}
assert((int)segtree.nodes.size() <= 4*numSectors + (iQuery+1)*4*30);
}
for (int iState = 0; iState < numStates; iState++) {
int loT = -1, hiT = Q; // T : queries in time [0, T]
while (hiT - loT > 1) {
int midT = loT + (hiT - loT) / 2;
int sum = 0;
for (int iSector : stateSectors[iState]) {
sum += segtree.query(0, iSector, 4*(midT+1));
}
if (sum >= stateNeed[iState]) {
hiT = midT;
}
else {
loT = midT;
}
}
if (hiT == Q) {
cout << "NIE\n";
}
else {
cout << hiT+1 << "\n";
}
}
}
