#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class Fenwick {
private:
vector<ll> val;
public:
Fenwick(int n) : val(n+1, 0) {}
// Adds v to index i
void add(int i, ll v) {
for (++i; i < val.size(); i += i & -i) {
val[i] += v;
}
}
// Calculates prefix sum up to index i
ll get(int i) {
ll res = 0;
for (++i; i > 0; i -= i & -i) {
res += val[i];
}
return res;
}
ll get(int a, int b) { return get(b) - get(a-1); }
};
// Segment tree for range minimum and addition.
class SegTree {
private:
const ll NEUT = 4 * (ll)1e18;
vector<ll> seg, tag;
int h = 1;
void apply(int i, ll v) {
seg[i] += v;
if (i < h) tag[i] += v;
}
void push(int i) {
if (tag[i] == 0) return;
apply(2*i, tag[i]);
apply(2*i+1, tag[i]);
tag[i] = 0;
}
ll combine(ll a, ll b) { return min(a, b); }
ll recGet(int a, int b, int i, int ia, int ib) {
if (ib <= a || b <= ia) return NEUT;
if (a <= ia && ib <= b) return seg[i];
push(i);
int im = (ia + ib) >> 1;
return combine(
recGet(a, b, 2*i, ia, im),
recGet(a, b, 2*i+1, im, ib));
}
void recApply(int a, int b, ll v, int i, int ia, int ib) {
if (ib <= a || b <= ia) return;
if (a <= ia && ib <= b) apply(i, v);
else {
push(i);
int im = (ia + ib) >> 1;
recApply(a, b, v, 2*i, ia, im);
recApply(a, b, v, 2*i+1, im, ib);
seg[i] = combine(seg[2*i], seg[2*i+1]);
}
}
int recFind(int a, int b, ll v, int i, int ia, int ib) {
if (seg[i] > v) return b;
if (b <= ia || ib <= a) return b;
if (ib == ia + 1) return ia;
push(i);
int im = (ia + ib) >> 1;
int off = recFind(a, b, v, 2*i, ia, im);
if (off < b) return off;
else return recFind(a, b, v, 2*i+1, im, ib);
}
public:
SegTree(int n) {
while(h < n) h *= 2;
seg.resize(2*h, 0);
tag.resize(h, 0);
}
ll rangeMin(int a, int b) { return recGet(a, b+1, 1, 0, h); }
void rangeAdd(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
int findNext(int a, int b, ll v) { return recFind(a, b+1, v, 1, 0, h); }
};
struct SegTreeBeats {
private:
struct Node {
ll val; // current value at this node (already capped locally)
ll lazyAdd; // pending "+=" to push to children
ll lazyCap; // pending "cap = min(cap, ...)" to push to children
Node(): val(0), lazyAdd(0), lazyCap(INF) {}
};
static constexpr ll INF = 4 * (ll)1e18;
int n;
std::vector<Node> st;
// Apply node's pending tags to itself, then push to children
inline void pass(int head, int l, int r) {
// 1) apply to current node
if (st[head].lazyAdd != 0 || st[head].lazyCap != INF) {
st[head].val = std::min(st[head].val + st[head].lazyAdd, st[head].lazyCap);
// 2) propagate to children
if (l != r) {
int L = head << 1, R = L | 1;
st[L].lazyAdd += st[head].lazyAdd;
st[R].lazyAdd += st[head].lazyAdd;
st[L].lazyCap = std::min(st[L].lazyCap, st[head].lazyCap);
st[R].lazyCap = std::min(st[R].lazyCap, st[head].lazyCap);
}
// 3) clear tags here
st[head].lazyAdd = 0;
st[head].lazyCap = INF;
}
}
// range add on [ql, qr) with “pure add” (cap = +INF)
void recAdd(int head, int l, int r, int ql, int qr, ll v) {
pass(head, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
st[head].lazyAdd += v; // queue the add
pass(head, l, r); // apply to current node (your style)
return;
}
int mid = (l + r) >> 1;
recAdd(head << 1, l, mid, ql, qr, v);
recAdd(head << 1 | 1, mid + 1, r, ql, qr, v);
// parent.val is not a merge; queries read exact node on coverage
// (like original beats version which returns node.cap directly)
// So no pull needed here.
}
// query max/cap on [ql, qr) — identical to original logic
ll recMax(int head, int l, int r, int ql, int qr) {
pass(head, l, r);
if (r < ql || qr < l) return -INF;
if (ql <= l && r <= qr) return st[head].val;
int mid = (l + r) >> 1;
return std::max(recMax(head << 1, l, mid, ql, qr),
recMax(head << 1 | 1, mid + 1, r, ql, qr));
}
// apply a global ceiling C at the root (like original apply(1,0,C))
inline void applyRootCap(ll C) {
st[1].lazyCap = std::min(st[1].lazyCap, C);
pass(1, 0, n - 1);
}
public:
// build with all zeros (same as the original beats sample)
explicit SegTreeBeats(int n): n(n) {
st.assign(4 * n + 5, Node());
}
// add v to [a, b] inclusive; then cap the whole structure by 0 at the root
// (exactly like original: rangeAdd(...) ; apply(1,0,0))
void rangeAdd(int a, int b, ll v) {
recAdd(1, 0, n - 1, a, b, v);
applyRootCap(0); // keep the original behavior: get(i) = min(A[i], 0)
}
// returns point value at i (min(A[i], current root cap))
ll get(int i) {
return recMax(1, 0, n - 1, i, i);
}
};
const string name = "test";
int main() {
if (fopen((name + ".inp").c_str(), "r"))
{
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
SegTreeBeats cur(n);
Fenwick tot(n+1);
vector<int> res;
vector<vector<pair<ll, int>>> qs(n);
vector<array<ll, 5>> ops(q);
for (int qi = 0; qi < q; ++qi) {
cin >> ops[qi][0];
ll a, b;
cin >> a >> b;
--a; --b;
ops[qi][1] = a; ops[qi][2] = b;
if (ops[qi][0] == 1) {
ll c, k;
cin >> c >> k;
ops[qi][3] = c; ops[qi][4] = k;
cur.rangeAdd(a, b, -k);
tot.add(a, k);
tot.add(b+1, -k);
} else if (ops[qi][0] == 2) {
ll k;
cin >> k;
ops[qi][3] = k;
cur.rangeAdd(a, b, k);
} else if (ops[qi][0] == 3) {
++b;
ll v = -cur.get(a);
int ind = res.size();
res.emplace_back(0);
if (v >= b) qs[a].emplace_back(tot.get(a) - (v - b), ind);
// cout << v << ' ' << tot.get(a) - (v - b) << '\n';
}
}
const ll INF = 1e18;
SegTree groups(n);
vector<int> inds(n, 0);
for (int i = 0; i < n; ++i) {
if (qs[i].empty()) {
groups.rangeAdd(i, i, INF);
} else {
sort(qs[i].begin(), qs[i].end());
groups.rangeAdd(i, i, qs[i][0].first);
}
}
for (int qi = 0; qi < q; ++qi) {
int t = ops[qi][0];
if (t == 1) {
ll a = ops[qi][1]; ll b = ops[qi][2];
ll c = ops[qi][3]; ll k = ops[qi][4];
groups.rangeAdd(a, b, -k);
while(true) {
int j = groups.findNext(0, n-1, 0);
if (j == n) break;
res[qs[j][inds[j]].second] = c;
++inds[j];
if (inds[j] >= qs[j].size()) {
groups.rangeAdd(j, j, INF);
} else {
groups.rangeAdd(j, j, qs[j][inds[j]].first - qs[j][inds[j] - 1].first);
}
}
}
}
for (auto c : res) cout << c << '\n';
}
