#include <bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
using namespace std;
const int tam = 300030;
const ll INF = 1e16;
unsigned long long T[2 * tam];
ll n, m, k;
vector<vll> G;
ll E[tam];
ll res[tam];
// Las queries (updates) se almacenan como:
// Q[i] = { {l, r}, val }
// (donde se debe aplicar update en BIT: update(l, val); update(r+1, -val);
// (además, si r < l se “envuelve” el intervalo)
vector<pair<pair<ll, ll>, ll>> Q;
// BIT (Fenwick Tree)
void update(int pos, int val) {
while (pos <= m) {
T[pos] += val;
pos += (pos & -pos);
}
}
ll query(ll pos) {
unsigned long long ans = 0;
while (pos > 0) {
ans += T[pos];
pos -= (pos & -pos);
}
return ans;
}
int main(){
fast;
ll x;
cin >> n >> m;
// G: para cada nodo (1-indexado) se guardan posiciones (1..m)
G.assign(n + 1, vll());
for (int i = 1; i <= m; i++){
cin >> x;
G[x].pb(i);
}
for (int i = 1; i <= n; i++){
cin >> E[i];
}
cin >> k;
for (int i = 0; i < k; i++){
ll l, r, val;
cin >> l >> r >> val;
Q.pb({{l, r}, val});
}
// Para cada nodo (consulta) definimos los límites de búsqueda.
// L[i] y R[i] son los índices en el arreglo de updates (Q), y la respuesta se guarda en ans[i]
vector<ll> L(n + 1, 0), R(n + 1, k - 1), ans(n + 1, k + 1);
bool updated = true;
// Mientras alguna consulta no esté resuelta (L[i] <= R[i])
while(updated){
updated = false;
// buckets[j] contendrá los nodos cuya búsqueda actual tiene mid = j.
vector<vll> buckets(k);
for (int i = 1; i <= n; i++){
if(L[i] <= R[i]){
updated = true;
ll mid = (L[i] + R[i]) / 2;
buckets[mid].pb(i);
}
}
// Reiniciamos BIT (T) a cero
memset(T, 0, sizeof(T));
// Se “aplican” los updates en orden (de 0 a k-1)
for (int j = 0; j < k; j++){
ll l = Q[j].F.F, r = Q[j].F.S, val = Q[j].S;
update(l, val);
// Si el intervalo se “envuelve”
if(r < l){
update(1, val);
update(m + 1, -val);
}
update(r + 1, -val);
// Para cada nodo asignado a este candidato medio (j)
for (ll node : buckets[j]){
ll sum = 0;
// Sumar las contribuciones en todas las posiciones indicadas en G[node]
for (auto pos : G[node]){
sum += query(pos);
if(sum >= 1e10) break; // corte temprano si la suma es grande
}
if(sum >= E[node]){
// Se cumple la condición, se puede intentar mejorar la respuesta
ans[node] = min(ans[node], (ll)j + 1);
R[node] = j - 1;
} else {
L[node] = j + 1;
}
}
}
}
// Se imprime la respuesta para cada nodo (consulta)
for (int i = 1; i <= n; i++){
if(ans[i] == k + 1)
cout << "NIE" << "\n";
else
cout << ans[i] << "\n";
}
return 0;
}
