Juanzhang

#include <bits/stdc++.h>
using namespace std;

#define nc getchar()
typedef long long ll;
const int maxn = 3e5 + 10;
int n, m, k, a[maxn], ans[maxn];
int q[maxn], q1[maxn], q2[maxn];

struct Query {
  int l, r, x;
} Q[maxn];

struct BIT {
  ll c[maxn];
  int T, t[maxn];
  void clr() { T++; }
  void add(int pos, int x) {
    for (; pos <= m; pos += pos & -pos) {
      t[pos] < T ? t[pos] = T, c[pos] = x : c[pos] += x;
    }
  }
  ll query(int pos) {
    ll res = 0;
    for (; pos; pos &= pos - 1) {
      res += t[pos] < T ? t[pos] = T, c[pos] = 0 : c[pos];
    }
    return res;
  }
  void upd(int pos) {
    int l = Q[pos].l, r = Q[pos].r, x = Q[pos].x;
    add(l, x), add(r + 1, -x);
    if (l > r) add(1, x);
  }
} bit;

vector <int> tid[maxn];

int read() {
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = x * 10 + c - 48, c = nc;
  return x;
}

void divide(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) {
      ans[q[i]] = ql;
    }
    return;
  }
  int mid = (ql + qr) >> 1;
  for (int i = ql; i <= mid; i++) {
    bit.upd(i);
  }
  int s1 = 0, s2 = 0;
  for (int i = l; i <= r; i++) {
    ll sum = 0;
    for (int pos : tid[q[i]]) {
      sum += bit.query(pos);
      if (sum > a[q[i]]) break;
    }
    if (a[q[i]] <= sum) {
      q1[++s1] = q[i];
    } else {
      q2[++s2] = q[i], a[q[i]] -= sum;
    }
  }
  for (int i = 1; i <= s1; i++) {
    q[l + i - 1] = q1[i];
  }
  for (int i = 1; i <= s2; i++) {
    q[l + s1 + i - 1] = q2[i];
  }
  bit.clr();
  divide(l, l + s1 - 1, ql, mid);
  divide(l + s1, r, mid + 1, qr);
}

int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    tid[read()].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = read(), q[i] = i;
  }
  k = read();
  for (int i = 1; i <= k; i++) {
    Q[i].l = read();
    Q[i].r = read();
    Q[i].x = read();
  }
  Q[++k] = Query{1, m, 1 << 30};
  divide(1, n, 1, k);
  for (int i = 1; i <= n; i++) {
    if (ans[i] < k) {
      printf("%d\n", ans[i]);
    } else {
      puts("NIE");
    }
  }
  return 0;
}