/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 250010;
const ll inf = 1e18;
struct node
{
ll min_val;
int min_lf, min_rf;
node(ll _min_val = inf, int _min_lf = -1, int _min_rf = -1)
{
min_val = _min_val;
min_lf = _min_lf;
min_rf = _min_rf;
}
};
node merge_nodes(node lf, node rf)
{
if (lf.min_val < rf.min_val)
return lf;
if (rf.min_val < lf.min_val)
return rf;
node cur = lf;
if (lf.min_rf == rf.min_lf - 1)
{
cur.min_rf = rf.min_rf;
}
return cur;
}
struct segment_tree
{
node tree[4 * maxn];
ll lazy[4 * maxn];
int tag[4 * maxn];
void push_lazy(int root, int left, int right)
{
tree[root].min_val += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
tag[root * 2] = tag[root * 2 + 1] = 1;
}
tag[root] = 0;
lazy[root] = 0;
}
void build(int root, int left, int right)
{
if (left == right)
{
tree[root].min_lf = left;
tree[root].min_rf = right;
tree[root].min_val = 0;
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
void update(int root, int left, int right, int qleft, int qright, ll cur)
{
if (tag[root])
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = cur;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update(root * 2, left, mid, qleft, qright, cur);
update(root * 2 + 1, mid + 1, right, qleft, qright, cur);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
if (tag[root])
push_lazy(root, left, right);
if (left > qright || right < qleft)
return node();
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_nodes(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
};
int readInt () {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
long long int read_int(){
char r;
bool start=false,neg=false;
long long int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}
int n, m, q;
void input()
{
n = readInt();
m = readInt();
q = readInt();
//cin >> n >> m >> q;
}
struct task
{
int idx;
ll pos;
task(int _idx = 0, ll _pos = 0)
{
idx = _idx;
pos = _pos;
}
};
struct bit
{
ll fen[maxn];
void update(int pos, ll val)
{
for (int i = pos; i < maxn; i += (i & -i))
fen[i] += val;
}
ll query(int pos)
{
ll sum = 0;
for (int i = pos; i > 0; i -= (i & -i))
sum += fen[i];
return sum;
}
void range_update(int l, int r, ll v)
{
update(l, v);
update(r + 1, - v);
}
int find_kth(ll to)
{
int pos = 0;
ll sum = 0;
for (int bit = 20; bit >= 0; bit --)
{
if (pos + (1 << bit) > maxn)
continue;
ll new_sum = sum + fen[pos + (1 << bit)];
if (new_sum < to)
{
pos = pos + (1 << bit);
sum = new_sum;
}
}
return pos + 1;
}
};
vector < task > ask[maxn];
segment_tree line_tree;
bit pass_tree;
int ans[maxn];
pair < int, ll > add[maxn];
vector < int > upd[maxn];
int query_cnt = 0;
void simulate()
{
line_tree.build(1, 1, n);
int t, l, r, c, a; /// careful overflow
ll k, b;
int cnt = 0;
for (int i = 1; i <= q; i ++)
{
///cin >> t;
t = readInt();
if (t == 1)
{
///cin >> l >> r >> c >> k;
l = readInt();
r = readInt();
c = readInt();
k = read_int();
line_tree.update(1, 1, n, l, r, k);
add[i] = {c, k};
upd[l].push_back(i);
upd[r + 1].push_back(-i);
}
else
if (t == 2)
{
///cin >> l >> r >> k;
l = readInt();
r = readInt();
k = read_int();
line_tree.update(1, 1, n, l, r, -k);
pass_tree.range_update(l, r, k);
node cur;
while(true)
{
cur = line_tree.query(1, 1, n, l, r);
if (cur.min_val >= 0)
break;
pass_tree.range_update(cur.min_lf, cur.min_rf, cur.min_val);
line_tree.update(1, 1, n, cur.min_lf, cur.min_rf, - cur.min_val);
cnt ++;
}
}
else
{
///cin >> a >> b;
a = readInt();
b = read_int();
query_cnt ++;
if (line_tree.query(1, 1, n, a, a).min_val < b)
{
ans[query_cnt] = 0;
}
else
{
///cout << "here " << query_cnt << " " << pass_tree.query(a) << " " << line_tree.query(1, 1, n, a, a).min_val << endl;
ask[a].push_back(task(query_cnt, pass_tree.query(a) + b));
}
}
}
assert(cnt <= 4 * q);
}
bit active;
void answer_tasks()
{
for (int i = 1; i <= n; i ++)
{
for (int cur : upd[i])
{
if (cur > 0)
{
active.update(cur, add[cur].second);
}
else
{
active.update(-cur, - add[-cur].second);
}
}
for (task cur : ask[i])
{
ans[cur.idx] = add[active.find_kth(cur.pos)].first;
///cout << cur.idx << " : " << cur.shop << " " << cur.pos << endl;
}
}
for (int i = 1; i <= query_cnt; i ++)
{
cout << ans[i] << endl;
}
}
void solve()
{
input();
simulate();
answer_tasks();
}
int main()
{
///freopen("test.txt", "r", stdin);
speed();
solve();
return 0;
}
