#include <iostream>
#include <vector>
#include <cmath>
#define MAXN 300000
#define MAXM 300000
#define MAXK 300000
using namespace std;
struct Event {
int L;
int R;
int A;
};
vector<int> O(MAXM);
vector<vector<int>> S(MAXN);
vector<int> P(MAXN);
vector<Event> E(MAXK);
vector<pair<int, int>> R(MAXN);
vector<int> ans(MAXN);
int N;
int M;
int K;
struct Node {
long long value;
long long lazyValue;
Node* left;
Node* right;
};
Node* root = new Node();
class LazySegmentTree {
public:
LazySegmentTree(Node*& current = root, int lo = 0, int hi = M - 1) {
if (current == nullptr)
current = new Node();
if (lo == hi)
return;
int mid = (lo + hi) / 2;
LazySegmentTree(current->left, lo, mid);
LazySegmentTree(current->right, mid + 1, hi);
}
void Update(const int qlo, const int qhi, const int x, Node* current = root, int lo = 0, int hi = M - 1) {
if (current->lazyValue != 0) {
current->value += (current->lazyValue) * (hi - lo + 1);
if (lo != hi) {
current->left->lazyValue += current->lazyValue;
current->right->lazyValue += current->lazyValue;
}
current->lazyValue = 0;
}
if (qlo > hi || qhi < lo)
return;
if (qlo <= lo && hi <= qhi) {
current->value += (long long)x * (hi - lo + 1);
if (lo != hi) {
current->left->lazyValue += x;
current->right->lazyValue += x;
}
return;
}
int mid = (lo + hi) / 2;
Update(qlo, qhi, x, current->left, lo, mid);
Update(qlo, qhi, x, current->right, mid + 1, hi);
current->value = (current->left != nullptr ? current->left->value : 0) + (current->right != nullptr ? current->right->value : 0);
}
long long Query(const int i, Node* current = root, int lo = 0, int hi = M - 1) {
if (current->lazyValue != 0) {
current->value += (current->lazyValue) * (hi - lo + 1);
if (lo != hi) {
current->left->lazyValue += current->lazyValue;
current->right->lazyValue += current->lazyValue;
}
current->lazyValue = 0;
}
if (lo == hi)
return current->value;
int mid = (lo + hi) / 2;
if (i <= mid)
return Query(i, current->left, lo, mid);
else
return Query(i, current->right, mid + 1, hi);
}
void deleteTree(Node* node) {
if (node == nullptr) return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
};
int main() {
cin >> N >> M;
for (int i = 0; i < M; ++i) {
cin >> O[i];
S[--O[i]].push_back(i);
}
for (int i = 0; i < N; ++i)
cin >> P[i];
cin >> K;
for (int i = 0; i < K; ++i) {
cin >> E[i].L >> E[i].R >> E[i].A;
--E[i].L;
--E[i].R;
}
fill(R.begin(), R.begin() + N, make_pair(0, K - 1));
for (int i = 0; i < ceil(log2(K)); ++i) {
vector<vector<int>> TS(K);
for (int j = 0; j < N; ++j)
if (R[j].first < R[j].second)
TS[(R[j].first + R[j].second) / 2].push_back(j);
LazySegmentTree T;
for (int j = 0; j < K; ++j) {
if (E[j].L <= E[j].R) {
T.Update(E[j].L, E[j].R, E[j].A);
}
else {
T.Update(E[j].L, M - 1, E[j].A);
T.Update(0, E[j].R, E[j].A);
}
for (int k : TS[j]) {
long long totalSamples = 0;
for (int l : S[k])
totalSamples += T.Query(l);
if (totalSamples >= P[k])
R[k].second = j;
else
R[k].first = j + 1;
}
}
if (i % 2 == 0)
T.deleteTree(root);
root = nullptr;
}
vector<vector<int>> TS(K);
for (int j = 0; j < N; ++j)
TS[R[j].first].push_back(j);
LazySegmentTree T;
for (int j = 0; j < K; ++j) {
if (E[j].L <= E[j].R) {
T.Update(E[j].L, E[j].R, E[j].A);
}
else {
T.Update(E[j].L, M - 1, E[j].A);
T.Update(0, E[j].R, E[j].A);
}
for (int k : TS[j]) {
long long totalSamples = 0;
for (int l : S[k])
totalSamples += T.Query(l);
if (totalSamples >= P[k])
ans[k] = j + 1;
else
ans[k] = -1;
}
}
for (int i = 0; i < N; ++i)
if (ans[i] == -1)
cout << "NIE" << endl;
else
cout << ans[i] << endl;
}
