#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
int n, m, q;
namespace sub12{
const int lim = 2e3 + 5;
queue<pair<int, int>>que[lim];
void solve(){
for(int _ = 0; _ < q; _++){
int type;
cin >> type;
if(type == 1){
int l, r, c, k;
cin >> l >> r >> c >> k;
for(int i = l; i <= r; i++){
que[i].push(make_pair(c, k));
}
}
else if(type == 2){
int l, r, k;
cin >> l >> r >> k;
for(int i = l; i <= r; i++){
for(int x = k; x > 0 && !que[i].empty(); ){
if(que[i].front().second <= x){
x -= que[i].front().second;
que[i].pop();
}
else{
que[i].front().second -= x;
break;
}
}
}
}
else{
int a, ans = 0;
ll b;
cin >> a >> b;
queue<pair<int, int>>temp = que[a];
while(!temp.empty()){
if(temp.front().second >= b){
ans = temp.front().first;
break;
}
b -= temp.front().second;
temp.pop();
}
cout << ans << "\n";
}
}
}
}
const int lim = 25e4 + 5;
const ll INF = 1e18 + 38;
pair<ll, ll>merge(pair<ll, ll>a, pair<ll, ll>b){
if(a.first > b.first){
swap(a, b);
}
minimize(a.second, a.first == b.first ? b.second : b.first);
return a;
}
pair<ll, ll>st[lim << 2];
ll lazy[lim << 2], add_chmax[lim << 2];
void propagate_add(int id, ll x){
st[id].first += x;
st[id].second += x;
lazy[id] += x;
}
void propagate_chmax(int id, ll x){
if(st[id].first < x){
add_chmax[id] += x - st[id].first;
st[id].first = x;
}
}
void push_down(int id){
propagate_add(id << 1, lazy[id]);
propagate_add(id << 1 | 1, lazy[id]);
lazy[id] = 0;
propagate_chmax(id << 1, st[id].first);
propagate_chmax(id << 1 | 1, st[id].first);
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate_add(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void chmax_zero(int id, int l, int r){
if(st[id].first > -1){
return;
}
if(st[id].second > 0){
propagate_chmax(id, 0);
return;
}
int m = (l + r) >> 1;
push_down(id);
chmax_zero(id << 1, l, m);
chmax_zero(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
namespace sub4{
void solve(){
fill(st, st + (lim << 2), make_pair(0, INF));
memset(lazy, 0, sizeof(lazy));
for(int _ = 0; _ < q; _++){
int type;
cin >> type;
if(type == 1){
int l, r, c, k;
cin >> l >> r >> c >> k;
update(1, 1, n, l, r, k);
}
else if(type == 2){
int l, r, k;
cin >> l >> r >> k;
update(1, 1, n, l, r, -k);
chmax_zero(1, 1, n);
}
else{
int a, id = 1, l = 1, r = n;
ll b;
cin >> a >> b;
while(l < r){
int m = (l + r) >> 1;
push_down(id);
id <<= 1;
if(m < a){
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
cout << (st[id].first < b ? "0\n" : "1\n");
}
}
}
}
struct Query{
int l, r, c, k;
ll b;
Query(){
this->c = this->b = -1;
}
};
vector<Query>query;
bool is_type(int id, int type){
if(type == 1){
return query[id].c != -1;
}
if(type == 2){
return query[id].c == -1 && query[id].b == -1;
}
return query[id].b != -1;
}
namespace sub3{
bool check_subtask(){
if(max(n, q) > 65000){
return false;
}
for(int i = 1; i <= q; i++){
if(is_type(i, 1) && (query[i].k > 1 || query[i].r - query[i].l > 10)){
return false;
}
}
return true;
}
void solve(){
set<int>s;
vector<deque<int>>d(n + 1);
for(int i = 1; i <= q; i++){
if(is_type(i, 1)){
for(int j = query[i].l; j <= query[i].r; s.insert(j++)){
d[j].push_back(query[i].c);
}
}
else if(is_type(i, 2)){
vector<int>trash;
for(set<int>::iterator it = s.lower_bound(query[i].l); it != s.end() && *it <= query[i].r; it++){
for(int j = 0; j < query[i].k && !d[*it].empty(); j++){
d[*it].pop_front();
}
if(d[*it].empty()){
trash.push_back(*it);
}
}
for(int& x : trash){
s.erase(x);
}
}
else{
cout << (d[query[i].l].size() < query[i].b ? 0 : d[query[i].l][query[i].b - 1]) << "\n";
}
}
}
}
namespace sub6{
bool check_subtask(){
if(max(n, q) > 65000){
return false;
}
for(int i = 1; i <= q; i++){
if(is_type(i, 2)){
return false;
}
}
return true;
}
vector<ll>bit;
void update(int p, int x){
for(; p <= n; p += p & -p){
bit[p] += x;
}
}
void update(int l, int r, int x){
update(l, x);
update(r + 1, -x);
}
ll get(int p){
ll ans = 0;
for(; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
void solve(){
bit.assign(n + 1, 0);
vector<int>low(q + 1, 1), high(q + 1, 0), ans(q + 1);
for(int i = 1; i <= q; i++){
if(is_type(i, 1)){
update(query[i].l, query[i].r, query[i].k);
}
else if(get(query[i].l) < query[i].b){
ans[i] = 0;
}
else{
high[i] = i - 1;
}
}
while(true){
bool flag = true;
vector<vector<int>>event(q + 1);
for(int i = 1; i <= q; i++){
if(low[i] <= high[i]){
event[(low[i] + high[i]) >> 1].push_back(i);
flag = false;
}
}
if(flag){
break;
}
fill(bit.begin(), bit.end(), 0);
for(int i = 1; i <= q; i++){
if(is_type(i, 1)){
update(query[i].l, query[i].r, query[i].k);
}
for(int& qid : event[i]){
if(get(query[qid].l) >= query[qid].b){
ans[qid] = query[i].c;
high[qid] = i - 1;
}
else{
low[qid] = i + 1;
}
}
}
}
for(int i = 1; i <= q; i++){
if(is_type(i, 3)){
cout << ans[i] << "\n";
}
}
}
}
namespace sub578{
ll qst[lim << 2], qlazy[lim << 2];
int ans[lim];
vector<pair<ll, int>>qid[lim];
void query_build(int id, int l, int r){
if(l == r){
qst[id] = -qid[l].back().first;
return;
}
int m = (l + r) >> 1;
query_build(id << 1, l, m);
query_build(id << 1 | 1, m + 1, r);
qst[id] = max(qst[id << 1], qst[id << 1 | 1]);
}
void query_propagate(int id, ll x){
qst[id] += x;
qlazy[id] += x;
}
void query_push_down(int id){
query_propagate(id << 1, qlazy[id]);
query_propagate(id << 1 | 1, qlazy[id]);
qlazy[id] = 0;
}
void query_update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
query_propagate(id, x);
return;
}
int m = (l + r) >> 1;
query_push_down(id);
query_update(id << 1, l, m, u, v, x);
query_update(id << 1 | 1, m + 1, r, u, v, x);
qst[id] = max(qst[id << 1], qst[id << 1 | 1]);
}
void query_refine(int id, int l, int r, const int c){
if(qst[id] < 0){
return;
}
if(l == r){
while(qst[id] > -1){
ans[qid[l].back().second] = c;
ll x = qid[l].back().first;
qid[l].pop_back();
qst[id] -= qid[l].back().first - x;
}
return;
}
int m = (l + r) >> 1;
query_push_down(id);
query_refine(id << 1, l, m, c);
query_refine(id << 1 | 1, m + 1, r, c);
qst[id] = max(qst[id << 1], qst[id << 1 | 1]);
}
ll query_get_point(int p){
int id = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
query_push_down(id);
id <<= 1;
if(m < p){
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
return qst[id];
}
void solve(){
for(int i = 1; i <= q; i++){
if(is_type(i, 1)){
update(1, 1, n, query[i].l, query[i].r, query[i].k);
}
else if(is_type(i, 2)){
update(1, 1, n, query[i].l, query[i].r, -query[i].k);
query_update(1, 1, n, query[i].l, query[i].r, query[i].k);
chmax_zero(1, 1, n);
}
else{
int id = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
push_down(id);
id <<= 1;
if(m < query[i].l){
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
qid[query[i].l].push_back(make_pair(query[i].b - add_chmax[id] + query_get_point(query[i].l), i));
}
}
for(int i = 1; i <= n; i++){
qid[i].push_back(make_pair(INF, -1));
sort(qid[i].begin(), qid[i].end(), greater<pair<ll, int>>());
}
memset(qlazy, 0, sizeof(qlazy));
memset(ans, 0, sizeof(ans));
query_build(1, 1, n);
for(int i = 1; i <= q; i++){
if(is_type(i, 1)){
query_update(1, 1, n, query[i].l, query[i].r, query[i].k);
query_refine(1, 1, n, query[i].c);
}
else if(is_type(i, 3)){
cout << ans[i] << "\n";
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> m >> q;
fill(st, st + (lim << 2), make_pair(0, INF));
memset(add_chmax, 0, sizeof(add_chmax));
memset(lazy, 0, sizeof(lazy));
if(max(n, q) <= 2000){
sub12::solve();
}
else if(m == 1){
sub4::solve();
}
else{
query.resize(q + 1);
for(int i = 1; i <= q; i++){
int type;
cin >> type;
if(type == 1){
cin >> query[i].l >> query[i].r >> query[i].c >> query[i].k;
}
else if(type == 2){
cin >> query[i].l >> query[i].r >> query[i].k;
}
else{
cin >> query[i].l >> query[i].b;
}
}
if(sub3::check_subtask()){
sub3::solve();
}
else if(sub6::check_subtask()){
sub6::solve();
}
else{
sub578::solve();
}
}
}
