#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
constexpr int MAXN = 1'000'007;
constexpr int INF = 2'000'000'000;
constexpr ll INFF = 1'000'000'000'000'000'000LL;
constexpr ll MOD = 998'244'353;
#define mkp make_pair
#define F first
#define S second
#define pb emplace_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
struct BIT {
int n;
vector<ll> d;
void init(int nn) {
n = nn;
d.resize(n + 1);
}
void add(int x, ll dd) {
for (int i = x; i <= n; i += (i & (-i)))
d[i] += dd;
}
int kth(int k) {
int ret = 0;
for (int i = 21; i >= 0; i--) {
if (ret + (1 << i) <= n && k - d[(1 << i) + ret] > 0)
k -= d[(1 << i) + ret], ret += (1 << i);
}
return ret + 1;
}
ll query(int x) {
if (x <= 0)
return 0LL;
ll ret = 0;
for (int i = x; i > 0; i -= (i & (-i)))
ret += d[i];
return ret;
}
} bit;
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
// assert(n >= 1 && n <= 300000);
// assert(m >= 1 && m <= 300000);
vector<int> a(m + 1), o(n + 1);
vector<vector<int>> reg(n + 1);
for (int i = 1; i <= m; i++) {
cin >> a[i], reg[a[i]].pb(i);
// assert(a[i] >= 1 && a[i] <= n);
}
for (int i = 1; i <= n; i++) {
cin >> o[i];
// assert(o[i] >= 1 && o[i] <= 1000000000);
}
int k;
cin >> k;
assert(k >= 1 && k <= 300000);
vector<tuple<int, int, int>> op(k);
for (auto &[l, r, x] : op) {
cin >> l >> r >> x;
// assert(l >= 1 && l <= m);
// assert(r >= 1 && r <= m);
// assert(x >= 1 && x <= 1000000000);
}
vector<int> ans(n + 1);
bit.init(m);
auto solve = [&](auto solve, int l, int r, vector<int> queries) -> void {
if (l == r) {
for (auto i : queries)
ans[i] = l;
return;
}
int mid = (l + r) >> 1;
for (int i = l; i <= mid; i++) {
auto [li, ri, x] = op[i];
if (li <= ri) {
bit.add(li, x);
bit.add(ri + 1, -x);
} else {
bit.add(li, x);
bit.add(1, x);
bit.add(ri + 1, -x);
}
}
vector<int> q1, q2;
for (auto i : queries) {
ll sum = 0;
for (int j : reg[i])
sum += bit.query(j);
if (sum >= o[i])
q1.pb(i);
else
q2.pb(i);
}
solve(solve, mid + 1, r, q2);
for (int i = l; i <= mid; i++) {
auto [li, ri, x] = op[i];
if (li <= ri) {
bit.add(li, -x);
bit.add(ri + 1, x);
} else {
bit.add(li, -x);
bit.add(1, -x);
bit.add(ri + 1, x);
}
}
solve(solve, l, mid, q1);
};
vector<int> q(n);
for (int i = 0; i < n; i++)
q[i] = i + 1;
solve(solve, 0, k, q);
for (int i = 1; i <= n; i++) {
if (ans[i] == k)
cout << "NIE\n";
else
cout << ans[i] + 1 << '\n';
}
}
/*
- How to come up with solutions? (https://hackmd.io/-3cIVAFSQMC3iJTh9EpszA)
- Play with some small examples.
- Make observations (or random guesses) by intuition.
- Try to find counterexamples of the "observations."
- Find the characteristics of an optimal solution.
- Try to solve simple cases.
- Brute force and print out the results.
- Pick a method (greedy, dp, d&c, ...)
- But DO NOT force algos on problems!
- IF YOU'RE STUCK, TRY SOMETHING ELSE! Make new observations!
- Before writing the solution:
- check TL/ML/correctness of samples/implementation details!
- Pre-submit:
- Did you make a typo when copying a template?
- Test more cases if unsure.
- Write a naive solution and check small cases.
- Submit the correct file.
- Debugging:
- General Debugging:
- Read the whole problem again.
- Think over the algorithm again.
- Go to the toilet.
- Wrong Answer:
- Any possible overflows?
- > `__int128` ?
- Try `-ftrapv` or `#pragma GCC optimize("trapv")`
- Floating point errors?
- > `long double` ?
- turn off math optimizations
- check for `==`, `>=`, `acos(1.000000001)`, etc.
- Did you forget to sort or unique?
- Generate large and worst "corner" cases.
- Check your `m` / `n`, `i` / `j`, `x` / `y` and `<` / `>`.
- Are everything initialized or reset properly?
- Are you sure about the STL thing you are using?
- Read cppreference.
- Print everything and run it on pen and paper.
- Time Limit Exceeded:
- Calculate your time complexity again.
- Does the program actually end?
- Check for `while(q.size())` etc.
- Test the largest cases locally.
- Did you do unnecessary stuff?
- e.g. pass vectors by value
- e.g. `memset` for every test case
- Is your constant factor reasonable?
- Runtime Error:
- Check memory usage.
- Forget to clear or destroy stuff?
- > `vector::shrink_to_fit()`
- Stack overflow?
- Bad pointer / array access?
- Try `-fsanitize=address`
- Division by zero? NaN's?
*/
