#include <bits/stdc++.h>
using namespace std;
int N, K, Q;
vector<int> values(1), weights(1), changes;
map< int, vector<int> > queries;
vector<long long> answers;
struct segment { int l, r, v, w; };
void evolve(vector<int> &knapsack, int v, int w) {
for (int k=K; k>=w; --k) knapsack[k] = max( knapsack[k], v + knapsack[k-w] );
}
long long output(const vector<int> &knapsack) {
long long answer = 0;
for (int k=K; k>=1; --k) answer = (answer*10000019 + knapsack[k]) % 1000000007;
return answer;
}
void solve(int lo, int hi, const vector<segment> &segments, vector<int> knapsack) {
if (hi-lo <= 1) return;
// find all segments we can already add to knapsack
vector<segment> remains;
for (const auto &seg : segments) {
if (seg.l <= lo && seg.r >= hi-1) {
evolve( knapsack, seg.v, seg.w );
} else {
remains.push_back(seg);
}
}
// solve for med if needed
int med = (lo+hi) / 2;
if (queries.count(med)) {
vector<int> med_knapsack = knapsack;
for (const auto &seg : remains) {
if (seg.l < med && seg.r >= med) {
evolve( med_knapsack, seg.v, seg.w );
}
}
long long curr = output(med_knapsack);
for (int q : queries[med]) answers[q] = curr;
}
// make recursive calls
vector<segment> left, right;
for (const auto &seg : remains) {
if (seg.l < med) left.push_back(seg);
if (seg.r > med) right.push_back(seg);
}
solve( lo, med, left, knapsack );
solve( med, hi, right, knapsack );
}
int main() {
cin >> N >> K;
for (int n=0; n<N; ++n) {
int v, w; cin >> v >> w;
values.push_back(v);
weights.push_back(w);
changes.push_back( +(n+1) );
}
cin >> Q;
for (int q=0; q<Q; ++q) {
int t; cin >> t;
if (t == 1) {
int v, w; cin >> v >> w;
values.push_back(v);
weights.push_back(w);
changes.push_back( +(values.size()-1) );
}
if (t == 2) {
int x; cin >> x;
changes.push_back( -x );
}
if (t == 3) {
queries[ changes.size() ].push_back(q);
}
}
answers.resize(Q,-1);
N = values.size();
vector<int> starts(N), ends(N,-1);
for (unsigned i=0; i<changes.size(); ++i)
if (changes[i]>0) starts[changes[i]]=i; else ends[-changes[i]]=i;
for (int n=1; n<=N; ++n) if (ends[n]==-1) { ends[n] = changes.size(); changes.push_back(-n); }
vector<segment> segments;
for (int n=1; n<N; ++n) segments.push_back( { starts[n], ends[n], values[n], weights[n] } );
for (int q : queries[ changes.size() ]) answers[q] = 0;
solve( 0, changes.size(), segments, vector<int>(K+1,0) );
for (auto a : answers) if (a != -1) cout << a << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgTiwgSywgUTsKdmVjdG9yPGludD4gdmFsdWVzKDEpLCB3ZWlnaHRzKDEpLCBjaGFuZ2VzOwptYXA8IGludCwgdmVjdG9yPGludD4gPiBxdWVyaWVzOwp2ZWN0b3I8bG9uZyBsb25nPiBhbnN3ZXJzOwoKc3RydWN0IHNlZ21lbnQgeyBpbnQgbCwgciwgdiwgdzsgfTsKCnZvaWQgZXZvbHZlKHZlY3RvcjxpbnQ+ICZrbmFwc2FjaywgaW50IHYsIGludCB3KSB7Cglmb3IgKGludCBrPUs7IGs+PXc7IC0taykga25hcHNhY2tba10gPSBtYXgoIGtuYXBzYWNrW2tdLCB2ICsga25hcHNhY2tbay13XSApOwp9Cgpsb25nIGxvbmcgb3V0cHV0KGNvbnN0IHZlY3RvcjxpbnQ+ICZrbmFwc2FjaykgewogICAgbG9uZyBsb25nIGFuc3dlciA9IDA7CiAgICBmb3IgKGludCBrPUs7IGs+PTE7IC0taykgYW5zd2VyID0gKGFuc3dlcioxMDAwMDAxOSArIGtuYXBzYWNrW2tdKSAlIDEwMDAwMDAwMDc7CiAgICByZXR1cm4gYW5zd2VyOwp9Cgp2b2lkIHNvbHZlKGludCBsbywgaW50IGhpLCBjb25zdCB2ZWN0b3I8c2VnbWVudD4gJnNlZ21lbnRzLCB2ZWN0b3I8aW50PiBrbmFwc2FjaykgewogICAgaWYgKGhpLWxvIDw9IDEpIHJldHVybjsKCiAgICAvLyBmaW5kIGFsbCBzZWdtZW50cyB3ZSBjYW4gYWxyZWFkeSBhZGQgdG8ga25hcHNhY2sKICAgIHZlY3RvcjxzZWdtZW50PiByZW1haW5zOwogICAgZm9yIChjb25zdCBhdXRvICZzZWcgOiBzZWdtZW50cykgewogICAgICAgIGlmIChzZWcubCA8PSBsbyAmJiBzZWcuciA+PSBoaS0xKSB7CiAgICAgICAgICAgIGV2b2x2ZSgga25hcHNhY2ssIHNlZy52LCBzZWcudyApOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHJlbWFpbnMucHVzaF9iYWNrKHNlZyk7CiAgICAgICAgfQogICAgfQoKICAgIC8vIHNvbHZlIGZvciBtZWQgaWYgbmVlZGVkCiAgICBpbnQgbWVkID0gKGxvK2hpKSAvIDI7CiAgICBpZiAocXVlcmllcy5jb3VudChtZWQpKSB7CiAgICAgICAgdmVjdG9yPGludD4gbWVkX2tuYXBzYWNrID0ga25hcHNhY2s7CiAgICAgICAgZm9yIChjb25zdCBhdXRvICZzZWcgOiByZW1haW5zKSB7CiAgICAgICAgICAgIGlmIChzZWcubCA8IG1lZCAmJiBzZWcuciA+PSBtZWQpIHsKICAgICAgICAgICAgICAgIGV2b2x2ZSggbWVkX2tuYXBzYWNrLCBzZWcudiwgc2VnLncgKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBsb25nIGxvbmcgY3VyciA9IG91dHB1dChtZWRfa25hcHNhY2spOwogICAgICAgIGZvciAoaW50IHEgOiBxdWVyaWVzW21lZF0pIGFuc3dlcnNbcV0gPSBjdXJyOwogICAgfQoKICAgIC8vIG1ha2UgcmVjdXJzaXZlIGNhbGxzCiAgICB2ZWN0b3I8c2VnbWVudD4gbGVmdCwgcmlnaHQ7CiAgICBmb3IgKGNvbnN0IGF1dG8gJnNlZyA6IHJlbWFpbnMpIHsKICAgICAgICBpZiAoc2VnLmwgPCBtZWQpIGxlZnQucHVzaF9iYWNrKHNlZyk7CiAgICAgICAgaWYgKHNlZy5yID4gbWVkKSByaWdodC5wdXNoX2JhY2soc2VnKTsKICAgIH0KICAgIHNvbHZlKCBsbywgbWVkLCBsZWZ0LCBrbmFwc2FjayApOwogICAgc29sdmUoIG1lZCwgaGksIHJpZ2h0LCBrbmFwc2FjayApOwp9CgppbnQgbWFpbigpIHsKICAgIGNpbiA+PiBOID4+IEs7CiAgICBmb3IgKGludCBuPTA7IG48TjsgKytuKSB7CiAgICAgICAgaW50IHYsIHc7IGNpbiA+PiB2ID4+IHc7CiAgICAgICAgdmFsdWVzLnB1c2hfYmFjayh2KTsKICAgICAgICB3ZWlnaHRzLnB1c2hfYmFjayh3KTsKICAgICAgICBjaGFuZ2VzLnB1c2hfYmFjayggKyhuKzEpICk7CiAgICB9CiAgICBjaW4gPj4gUTsKICAgIGZvciAoaW50IHE9MDsgcTxROyArK3EpIHsKICAgICAgICBpbnQgdDsgY2luID4+IHQ7CiAgICAgICAgaWYgKHQgPT0gMSkgewogICAgICAgICAgICBpbnQgdiwgdzsgY2luID4+IHYgPj4gdzsKICAgICAgICAgICAgdmFsdWVzLnB1c2hfYmFjayh2KTsKICAgICAgICAgICAgd2VpZ2h0cy5wdXNoX2JhY2sodyk7CiAgICAgICAgICAgIGNoYW5nZXMucHVzaF9iYWNrKCArKHZhbHVlcy5zaXplKCktMSkgKTsKICAgICAgICB9CiAgICAgICAgaWYgKHQgPT0gMikgewogICAgICAgICAgICBpbnQgeDsgY2luID4+IHg7CiAgICAgICAgICAgIGNoYW5nZXMucHVzaF9iYWNrKCAteCApOwogICAgICAgIH0KICAgICAgICBpZiAodCA9PSAzKSB7CiAgICAgICAgICAgIHF1ZXJpZXNbIGNoYW5nZXMuc2l6ZSgpIF0ucHVzaF9iYWNrKHEpOwogICAgICAgIH0KICAgIH0KCiAgICBhbnN3ZXJzLnJlc2l6ZShRLC0xKTsKCiAgICBOID0gdmFsdWVzLnNpemUoKTsKICAgIHZlY3RvcjxpbnQ+IHN0YXJ0cyhOKSwgZW5kcyhOLC0xKTsKICAgIGZvciAodW5zaWduZWQgaT0wOyBpPGNoYW5nZXMuc2l6ZSgpOyArK2kpCiAgICAJaWYgKGNoYW5nZXNbaV0+MCkgc3RhcnRzW2NoYW5nZXNbaV1dPWk7IGVsc2UgZW5kc1stY2hhbmdlc1tpXV09aTsKICAgIGZvciAoaW50IG49MTsgbjw9TjsgKytuKSBpZiAoZW5kc1tuXT09LTEpIHsgZW5kc1tuXSA9IGNoYW5nZXMuc2l6ZSgpOyBjaGFuZ2VzLnB1c2hfYmFjaygtbik7IH0KCiAgICB2ZWN0b3I8c2VnbWVudD4gc2VnbWVudHM7CiAgICBmb3IgKGludCBuPTE7IG48TjsgKytuKSBzZWdtZW50cy5wdXNoX2JhY2soIHsgc3RhcnRzW25dLCBlbmRzW25dLCB2YWx1ZXNbbl0sIHdlaWdodHNbbl0gfSApOwoKICAgIGZvciAoaW50IHEgOiBxdWVyaWVzWyBjaGFuZ2VzLnNpemUoKSBdKSBhbnN3ZXJzW3FdID0gMDsKCiAgICBzb2x2ZSggMCwgY2hhbmdlcy5zaXplKCksIHNlZ21lbnRzLCB2ZWN0b3I8aW50PihLKzEsMCkgKTsKCiAgICBmb3IgKGF1dG8gYSA6IGFuc3dlcnMpIGlmIChhICE9IC0xKSBjb3V0IDw8IGEgPDwgZW5kbDsKfQ==