!Recursive Parallel Binary Search

#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <string>
#include <cstring>
#include <set>

using namespace std;

typedef long long ll;
typedef double ld;

const int N = 300001;

vector<int> owner[N];
ll need[N];
int ql[N], qr[N];
ll a[N];
int ans[N];
const int T = 2000001;
ll tree[T];

void upd(int v, int l, int r, int ql, int qr, ll val)
{
    if (r <= l|| l >= qr || ql >= r)
        return;
    if (ql <= l && r <= qr)
    {
        tree[v] += val;
        return;
    }
    int mid = (r + l) / 2;
    upd(2 * v, l, mid, ql, qr, val);
    upd(2 * v + 1, mid, r, ql, qr, val);
}

int m;

ll find(int v, int l, int r, int q)
{
    if (l + 1 == r)
        return tree[v];
    int mid = (r + l) / 2;
    if (q < mid)
        return tree[v] + find(2 * v, l, mid, q);
    return tree[v] + find(2 * v + 1, mid, r, q);
}

void divide(int l, int r, vector<int> v) // челики, у которых ответ на полуинтервале [l;r)
{
    if (!v.size())
        return;
    if (r <= l)
        return;
    if (l + 1 == r)
    {
        for (int i : v)
            ans[i] = l;
        return;
    }
    vector<int> left, right;
    int mid = (r + l) / 2;

    for (int i = l; i < mid; i++)
        if (ql[i] < qr[i])
            upd(1, 0, m, ql[i], qr[i], a[i]);
        else
            upd(1, 0, m, ql[i], m, a[i]), upd(1, 0, m, 0, qr[i], a[i]);


    for (int i : v)
    {
        ll cur = 0;
        for (int j : owner[i])
        {
            cur += find(1, 0, m, j);
            if (cur >= need[i])
                break;
        }
        if (cur >= need[i])
            left.push_back(i);
        else
            right.push_back(i);
    }
    v.clear();
    divide(mid, r, right);
    right.clear();

    for (int i = l; i < mid; i++)
        if (ql[i] < qr[i])
            upd(1, 0, m, ql[i], qr[i], -a[i]);
        else
            upd(1, 0, m, ql[i], m, -a[i]), upd(1, 0, m, 0, qr[i], -a[i]);

    divide(l, mid, left);
    left.clear();
 }

int main()
{
   // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    int n;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        x--;
        owner[x].push_back(i);
    }
    for (int i = 0; i < n; i++)
        ans[i] = -1;
    for (int i = 0; i < n; i++)
        cin >> need[i];
    vector<int> kek;
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
        cin >> ql[i] >> qr[i] >> a[i], ql[i]--;
    for (int i = 0; i < n; i++)
        kek.push_back(i);
    divide(0, k + 1, kek);
    for (int i = 0; i < n; i++)
    {
        if (ans[i] == k)
            cout << "NIE\n";
        else
            cout << ans[i] + 1 << "\n";
    }
    return 0;
}