#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; struct SegmentTreeBeats { static constexpr ll INF = (ll)1e18; int n; vector<ll> mn, smn, lazy; vector<int> cnt; SegmentTreeBeats(int _n) : n(_n) { mn.assign(4*n, 0); smn.assign(4*n, INF); cnt.assign(4*n, 1); lazy.assign(4*n, 0); } void push_add(int v, ll x) { mn[v] += x; if (smn[v] < INF) smn[v] += x; lazy[v] += x; } void push_chmax(int v, ll x) { if (mn[v] < x) { mn[v] = x; } } void push(int v) { if (lazy[v]) { push_add(v<<1, lazy[v]); push_add(v<<1|1, lazy[v]); lazy[v] = 0; } push_chmax(v<<1, mn[v]); push_chmax(v<<1|1, mn[v]); } void pull(int v) { if (mn[v<<1] < mn[v<<1|1]) { mn[v] = mn[v<<1]; cnt[v] = cnt[v<<1]; smn[v] = min(mn[v<<1|1], smn[v<<1]); } else if (mn[v<<1] > mn[v<<1|1]) { mn[v] = mn[v<<1|1]; cnt[v] = cnt[v<<1|1]; smn[v] = min(mn[v<<1], smn[v<<1|1]); } else { mn[v] = mn[v<<1]; cnt[v] = cnt[v<<1] + cnt[v<<1|1]; smn[v] = min(smn[v<<1], smn[v<<1|1]); } } void range_add(int v, int l, int r, int ql, int qr, ll x) { if (r < ql || qr < l) return; if (ql <= l && r <= qr) { push_add(v, x); return; } push(v); int m = (l+r)>>1; range_add(v<<1, l, m, ql, qr, x); range_add(v<<1|1, m+1, r, ql, qr, x); pull(v); } void range_chmax(int v, int l, int r, ll x) { if (mn[v] >= x) return; if (smn[v] > x) { mn[v] = x; return; } push(v); int m = (l+r)>>1; range_chmax(v<<1, l, m, x); range_chmax(v<<1|1, m+1, r, x); pull(v); } ll Q(int v, int l, int r, int pos) { if (l == r) return mn[v]; push(v); int m = (l+r)>>1; if (pos <= m) return Q(v<<1, l, m, pos); else return Q(v<<1|1, m+1, r, pos); } // API void add(int l, int r, ll x) { range_add(1, 0, n-1, l, r, x); } void max_with_zero() { range_chmax(1, 0, n-1, 0); } ll query(int pos) { return Q(1, 0, n-1, pos); } }; struct Block { ll type,amount,time; }; struct SegTree { ll base; vector<ll> T, L; SegTree(ll n) { ll lvl = __lg(n) + 1; base = 1<<lvl; T.assign(2*base, 0); L.assign(2*base, 0); } void push(ll v, ll l, ll r) { if(L[v]==0 || r>=2*base) return; T[l] += L[v]; T[r] += L[v]; L[l] += L[v]; L[r] += L[v]; L[v] = 0; } void update(ll v, ll a, ll b, ll l, ll r, ll val) { if(b < l || r < a) return; if(l<=a && b<=r) { T[v] += val; L[v] += val; return; } ll lewy = 2*v; ll prawy = 2*v+1; ll mid=(a+b)/2; push(v, lewy, prawy); update(lewy,a,mid,l,r,val); update(prawy,mid+1,b,l,r,val); T[v] = max(T[lewy], T[prawy]); } ll find(ll v, ll a, ll b, ll x) { if(a==b) return v - base; ll lewy = 2*v; ll prawy = 2*v+1; ll mid=(a+b)/2; push(v, lewy, prawy); if(T[lewy] >= x) return find(lewy,a,mid,x); return find(prawy,mid+1,b,x); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,m,q; cin >> n >> m >> q; vector<ll> ans; vector<vector<pair<ll, ll>>> query(n+1); vector<vector<Block>> bloki_add(n+1), bloki_del(n+2); SegmentTreeBeats stb(n), stb2(n); for(ll t=0; t<q; ++t) { ll T; cin >> T; if(T==1) { ll l,r,c,k; cin >> l >> r >> c >> k; --l; --r; bloki_add[l].push_back({c,k,t}); bloki_del[r+1].push_back({c,k,t}); stb.add(l,r,k); stb2.add(l,r,k); } else if(T==2) { ll l,r,k; cin >> l >> r >> k; --l; --r; stb.add(l,r,-k); } else { ll a,b; cin >> a >> b; --a; ans.push_back(-1); if(stb.query(a) < b) ans.back() = 0; else query[a].push_back({b + stb2.query(a) - stb.query(a), ans.size()-1}); } stb.max_with_zero(); } SegTree st(2*q+1); vector<ll> typ(2*q+1); for(ll i=0; i<n; ++i) { for(auto[c,k,t] : bloki_add[i]) { typ[t] = c; st.update(1,0,st.base-1,t,st.base-1,k); } for(auto[c,k,t] : bloki_del[i]) { typ[t] = -1; st.update(1,0,st.base-1,t,st.base-1,-k); } for(auto[poz, idx] : query[i]) ans[idx] = typ[st.find(1,0,st.base-1,poz)]; } for(auto x : ans) cout << x << '\n'; return 0; }