#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
const int tam = 300030;
const ll INF = 1e16;
// BIT (Fenwick Tree)
unsigned long long T[2 * tam];
ll n, m, k;
vector<vll> G; // Para cada nodo (1-indexado) se guardan posiciones (en [1, m])
ll E[tam]; // Para cada nodo se tiene un umbral
ll res[tam]; // Respuesta para cada nodo (mínimo update en el que se cumple la condición)
// Las queries (updates) se almacenan en Q:
// Q[i] = { {l, r}, val } indica que se debe aplicar:
// update(l, val); update(r+1, -val);
// (además, si r < l se “envuelve” el intervalo)
vector<pair<pair<ll,ll>, ll>> Q;
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;
}
// Definimos dos tipos de acción para simular la recursión
enum ActionType { PROCESS, ROLLBACK };
// Una acción de la pila contendrá:
// - Para PROCESS: el intervalo de updates [b, e] y la lista de nodos a evaluar.
// - Para ROLLBACK: el intervalo [b, mid] que se usó en un PROCESS para luego deshacer los BIT updates.
struct Action {
ActionType type;
ll b, e, mid; // Para PROCESS: se usan b y e; para ROLLBACK: se usan b y mid (e no importa)
vll nodes; // Solo para PROCESS.
};
// Función iterativa de parallel binary search usando una pila (stack)
void parallel_stack() {
stack<Action> st;
// Estado inicial: buscamos en el rango de updates [0, k-1] para todos los nodos (1..n)
vll allNodes;
for (int i = 1; i <= n; i++) {
allNodes.pb(i);
}
st.push({PROCESS, 0, k - 1, -1, allNodes});
while (!st.empty()) {
Action cur = st.top();
st.pop();
if (cur.type == PROCESS) {
// Si no hay nodos o el intervalo de updates es inválido, saltamos
if (cur.nodes.empty() || cur.b > cur.e) continue;
ll mid = (cur.b + cur.e) / 2;
// Aplicamos los BIT updates para los updates en el intervalo [cur.b, mid]
for (ll i = cur.b; i <= mid; i++) {
ll l = Q[i].F.F, r = Q[i].F.S, val = Q[i].S;
update(l, val);
if (r < l) {
update(1, val);
update(m + 1, -val);
}
update(r + 1, -val);
}
// Separamos los nodos en dos grupos:
// A: aquellos que cumplen la condición (suma >= E[node])
// B: los que no cumplen.
vll A, B;
for (ll node : cur.nodes) {
ll sum = 0;
for (auto pos : G[node]) {
sum += query(pos);
if (sum >= 1e10) break; // corte temprano
}
if (sum >= E[node]) {
A.pb(node);
res[node] = min(res[node], mid + 1); // mid es 0-indexado, guardamos mid+1
} else {
B.pb(node);
}
}
// Para simular la recursión:
// Se debe procesar primero el branch derecho (con BIT aún aplicado),
// luego hacer rollback de los updates, y finalmente procesar el branch izquierdo.
// Debido a LIFO, empujamos en el orden inverso:
// 1. Push PROCESS para el branch izquierdo ([cur.b, mid-1], nodos A) si no está vacío.
// 2. Push ROLLBACK (para deshacer updates en [cur.b, mid]).
// 3. Push PROCESS para el branch derecho ([mid+1, cur.e], nodos B) si no está vacío.
if (!A.empty() && cur.b <= mid - 1) {
st.push({PROCESS, cur.b, mid - 1, -1, A});
}
st.push({ROLLBACK, cur.b, 0, mid, {}}); // ROLLBACK: guardamos b y mid.
if (!B.empty() && mid + 1 <= cur.e) {
st.push({PROCESS, mid + 1, cur.e, -1, B});
}
} else { // Acción ROLLBACK: deshacemos los BIT updates aplicados en [cur.b, cur.mid]
for (ll i = cur.b; i <= cur.mid; i++) {
ll l = Q[i].F.F, r = Q[i].F.S;
ll val = -Q[i].S; // Inverso del valor aplicado anteriormente
update(l, val);
if (r < l) {
update(1, val);
update(m + 1, -val);
}
update(r + 1, -val);
}
}
}
}
int main(){
fast;
ll x;
cin >> n >> m;
// Para cada nodo (1 a n) se guarda una lista de posiciones (índices de update) que le afectan.
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});
}
// Inicializamos res para cada nodo; si no se alcanza, se mantiene k+1
for (int i = 0; i <= n; i++) {
res[i] = k + 1;
}
// Aseguramos que el BIT esté en cero
memset(T, 0, sizeof(T));
parallel_stack();
for (int i = 1; i <= n; i++){
if (res[i] == k + 1)
cout << "NIE" << "\n";
else
cout << res[i] << "\n";
}
return 0;
}
