#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <array>
#include <unordered_set>
#include <stack>
using namespace std;
#define SZ(a) (int)(a).size()
typedef long long ll;
typedef ll E;
E mkE(int x, int y) {
return ((ll)x)<<32 | (ll)y;
}
int fst(E e) {
return (int)(e>>32);
}
int snd(E e) {
return (int)(e & (1ll<<32)-1);
}
struct O {
bool tp;
E e;
pair<int, int> b;
O() {
}
O(bool _tp, E _e) : tp(_tp) , e(_e) {
}
O(bool _tp, pair<int, int> _b) : tp(_tp) , b(_b) {
}
};
const auto maxn = (int)2e5;
const auto maxD = (int)2e5;
const auto maxsz = (int)1e9;
const auto maxtg = (ll)maxn*maxsz;
struct DSU {
struct A {
ll* p;
ll s;
A(ll* _p, ll _s) : p(_p), s(_s) {
}
};
int n;
vector<ll> pars;
vector<ll> szs;
vector<O> os;
bool rec;
int time;
stack<A> hist;
stack<int> marks;
void assign(int _n) {
n = _n;
pars.assign(n, -1);
szs.resize(n);
rec = false;
time = 0;
}
ll store(ll* p, ll x) {
if (rec && *p != x) {
hist.emplace(p, *p);
}
return *p = x;
}
ll find(ll u) {
auto& pu = pars[u];
return pu < 0 ? u : store(&pu, find(pu));
}
void uni(ll u, ll v) {
auto ru = find(u);
auto rv = find(v);
if (ru != rv) {
if (rand() & 1) {
swap(ru, rv);
}
store(&pars[rv], ru);
store(&szs[ru], szs[ru]+szs[rv]);
}
}
void upd(ll u, ll x) {
auto ru = find(u);
store(&szs[ru], szs[ru]+x);
}
void move() {
auto& o = os[time];
if (o.tp) {
uni(fst(o.e), snd(o.e));
}
else {
upd(o.b.first, o.b.second);
}
time++;
marks.push(SZ(hist));
}
void jto(int time1) {
if (time1 >= time) {
while (time < time1) {
move();
}
}
else {
while (SZ(marks) > time1) {
marks.pop();
}
auto m = marks.empty() ? 0 : marks.top();
while (SZ(hist) > m) {
*hist.top().p = hist.top().s;
hist.pop();
}
time = time1;
}
}
};
struct Q {
int i;
array<int, 2> us;
ll tg;
};
DSU dsu;
vector<Q> qs;
vector<int> ans;
bool f(Q q) {
auto s = 0ll;
for (auto u: q.us) {
s += dsu.szs[dsu.find(u)];
}
return s < q.tg;
}
int split(int l, int u, int t) {
dsu.jto(t);
while (l != u) {
if (f(qs[l])) {
swap(qs[l], qs[--u]);
}
else {
l++;
}
}
return l;
}
void bsearch(int l, int u, int lo, int up) {
if (l == u) {
return;
}
if (lo+1 == up) {
for (auto i = l; i < u; i++) {
ans[qs[i].i] = lo;
}
return;
}
auto mi = (lo+up)/2;
auto m = split(l, u, mi);
bsearch(l, m, lo, mi);
bsearch(m, u, mi, up);
}
int main() {
cin.sync_with_stdio(false);
int n, m, D, S;
cin >> n >> m >> D >> S;
dsu.assign(n);
for (auto u = 0; u < n; u++) {
cin >> dsu.szs[u];
}
unordered_set<E> es;
for (auto i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--; v--;
if (u > v) {
swap(u, v);
}
es.insert(mkE(u, v));
}
dsu.os.resize(D);
for (auto t = D-1; t >= 0; t--) {
int tmp;
cin >> tmp;
auto tp = tmp == 1;
if (tp) {
int u, v;
cin >> u >> v;
u--; v--;
if (u > v) {
swap(u, v);
}
auto e = mkE(u, v);
es.erase(e);
dsu.os[t] = O(tp, e);
}
else {
int u, x;
cin >> u >> x;
u--;
dsu.szs[u] -= x;
dsu.os[t] = O(tp, make_pair(u, x));
}
}
for (auto e: es) {
dsu.uni(fst(e), snd(e));
}
dsu.rec = true;
qs.resize(S);
for (auto i = 0; i < S; i++) {
int u, v;
cin >> u >> v;
u--; v--;
ll tg;
cin >> tg;
qs[i] = {i, {u, v}, tg};
}
ans.resize(S);
bsearch(0, S, -1, D+1);
for (auto i = 0; i < S; i++) {
printf("%d\n", D-1-ans[i]);
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YXJyYXk+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8c3RhY2s+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgU1ooYSkgKGludCkoYSkuc2l6ZSgpCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIGxsIEU7CiAKRSBta0UoaW50IHgsIGludCB5KSB7CglyZXR1cm4gKChsbCl4KTw8MzIgfCAobGwpeTsKfQogCmludCBmc3QoRSBlKSB7CglyZXR1cm4gKGludCkoZT4+MzIpOwp9CiAKaW50IHNuZChFIGUpIHsKCXJldHVybiAoaW50KShlICYgKDFsbDw8MzIpLTEpOwp9CiAKc3RydWN0IE8gewogCglib29sIHRwOwoJRSBlOwoJcGFpcjxpbnQsIGludD4gYjsKIAoJTygpIHsKCX0KIAoJTyhib29sIF90cCwgRSBfZSkgOiB0cChfdHApICwgZShfZSkgewoJfQogCglPKGJvb2wgX3RwLCBwYWlyPGludCwgaW50PiBfYikgOiB0cChfdHApICwgYihfYikgewoJfQogCn07CiAKY29uc3QgYXV0byBtYXhuID0gKGludCkyZTU7CmNvbnN0IGF1dG8gbWF4RCA9IChpbnQpMmU1Owpjb25zdCBhdXRvIG1heHN6ID0gKGludCkxZTk7CmNvbnN0IGF1dG8gbWF4dGcgPSAobGwpbWF4biptYXhzejsKIApzdHJ1Y3QgRFNVIHsKIAoJc3RydWN0IEEgewoJCWxsKiBwOwoJCWxsIHM7CgkJQShsbCogX3AsIGxsIF9zKSA6IHAoX3ApLCBzKF9zKSB7CgkJfQoJfTsKIAoJaW50IG47Cgl2ZWN0b3I8bGw+IHBhcnM7Cgl2ZWN0b3I8bGw+IHN6czsKCXZlY3RvcjxPPiBvczsKCWJvb2wgcmVjOwoJaW50IHRpbWU7CglzdGFjazxBPiBoaXN0OwoJc3RhY2s8aW50PiBtYXJrczsKIAoJdm9pZCBhc3NpZ24oaW50IF9uKSB7CgkJbiA9IF9uOwoJCXBhcnMuYXNzaWduKG4sIC0xKTsKCQlzenMucmVzaXplKG4pOwoJCXJlYyA9IGZhbHNlOwoJCXRpbWUgPSAwOwoJfQogCglsbCBzdG9yZShsbCogcCwgbGwgeCkgewoJCWlmIChyZWMgJiYgKnAgIT0geCkgewoJCQloaXN0LmVtcGxhY2UocCwgKnApOwoJCX0KCQlyZXR1cm4gKnAgPSB4OwoJfQogCglsbCBmaW5kKGxsIHUpIHsKCQlhdXRvJiBwdSA9IHBhcnNbdV07CgkJcmV0dXJuIHB1IDwgMCA/IHUgOiBzdG9yZSgmcHUsIGZpbmQocHUpKTsKCX0KIAoJdm9pZCB1bmkobGwgdSwgbGwgdikgewoJCWF1dG8gcnUgPSBmaW5kKHUpOwoJCWF1dG8gcnYgPSBmaW5kKHYpOwoJCWlmIChydSAhPSBydikgewoJCQlpZiAocmFuZCgpICYgMSkgewoJCQkJc3dhcChydSwgcnYpOwoJCQl9CgkJCXN0b3JlKCZwYXJzW3J2XSwgcnUpOwoJCQlzdG9yZSgmc3pzW3J1XSwgIHN6c1tydV0rc3pzW3J2XSk7CgkJfQoJfQogCgl2b2lkIHVwZChsbCB1LCBsbCB4KSB7CgkJYXV0byBydSA9IGZpbmQodSk7CgkJc3RvcmUoJnN6c1tydV0sIHN6c1tydV0reCk7Cgl9CiAKCXZvaWQgbW92ZSgpIHsKCQlhdXRvJiBvID0gb3NbdGltZV07CgkJaWYgKG8udHApIHsKCQkJdW5pKGZzdChvLmUpLCBzbmQoby5lKSk7CgkJfQoJCWVsc2UgewoJCQl1cGQoby5iLmZpcnN0LCBvLmIuc2Vjb25kKTsKCQl9CgkJdGltZSsrOwoJCW1hcmtzLnB1c2goU1ooaGlzdCkpOwoJfQogCgl2b2lkIGp0byhpbnQgdGltZTEpIHsKCQlpZiAodGltZTEgPj0gdGltZSkgewoJCQl3aGlsZSAodGltZSA8IHRpbWUxKSB7CgkJCQltb3ZlKCk7CgkJCX0KCQl9CgkJZWxzZSB7CgkJCXdoaWxlIChTWihtYXJrcykgPiB0aW1lMSkgewoJCQkJbWFya3MucG9wKCk7CgkJCX0KCQkJYXV0byBtID0gbWFya3MuZW1wdHkoKSA/IDAgOiBtYXJrcy50b3AoKTsKCQkJd2hpbGUgKFNaKGhpc3QpID4gbSkgewoJCQkJKmhpc3QudG9wKCkucCA9IGhpc3QudG9wKCkuczsKCQkJCWhpc3QucG9wKCk7CgkJCX0KCQkJdGltZSA9IHRpbWUxOwoJCX0KCX0KIAp9OwogCnN0cnVjdCBRIHsKCWludCBpOwoJYXJyYXk8aW50LCAyPiB1czsKCWxsIHRnOwp9OwogCkRTVSBkc3U7CnZlY3RvcjxRPiBxczsKdmVjdG9yPGludD4gYW5zOwogCmJvb2wgZihRIHEpIHsKCWF1dG8gcyA9IDBsbDsKCWZvciAoYXV0byB1OiBxLnVzKSB7CgkJcyArPSBkc3Uuc3pzW2RzdS5maW5kKHUpXTsKCX0KCXJldHVybiBzIDwgcS50ZzsKfQogCmludCBzcGxpdChpbnQgbCwgaW50IHUsIGludCB0KSB7Cglkc3UuanRvKHQpOwoJd2hpbGUgKGwgIT0gdSkgewoJCWlmIChmKHFzW2xdKSkgewoJCQlzd2FwKHFzW2xdLCBxc1stLXVdKTsKCQl9CgkJZWxzZSB7CgkJCWwrKzsKCQl9Cgl9CglyZXR1cm4gbDsKfQogCnZvaWQgYnNlYXJjaChpbnQgbCwgaW50IHUsIGludCBsbywgaW50IHVwKSB7CglpZiAobCA9PSB1KSB7CgkJcmV0dXJuOwoJfQoJaWYgKGxvKzEgPT0gdXApIHsKCQlmb3IgKGF1dG8gaSA9IGw7IGkgPCB1OyBpKyspIHsKCQkJYW5zW3FzW2ldLmldID0gbG87CgkJfQoJCXJldHVybjsKCX0KCWF1dG8gbWkgPSAobG8rdXApLzI7CglhdXRvIG0gPSBzcGxpdChsLCB1LCBtaSk7Cglic2VhcmNoKGwsIG0sIGxvLCBtaSk7Cglic2VhcmNoKG0sIHUsIG1pLCB1cCk7Cn0KIAppbnQgbWFpbigpIHsKCWNpbi5zeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJaW50IG4sIG0sIEQsIFM7CgljaW4gPj4gbiA+PiBtID4+IEQgPj4gUzsKCWRzdS5hc3NpZ24obik7Cglmb3IgKGF1dG8gdSA9IDA7IHUgPCBuOyB1KyspIHsKCQljaW4gPj4gZHN1LnN6c1t1XTsKCX0KCXVub3JkZXJlZF9zZXQ8RT4gZXM7Cglmb3IgKGF1dG8gaSA9IDA7IGkgPCBtOyBpKyspIHsKCQlpbnQgdSwgdjsKCQljaW4gPj4gdSA+PiB2OwoJCXUtLTsgdi0tOwoJCWlmICh1ID4gdikgewoJCQlzd2FwKHUsIHYpOwoJCX0KCQllcy5pbnNlcnQobWtFKHUsIHYpKTsKCX0KCWRzdS5vcy5yZXNpemUoRCk7Cglmb3IgKGF1dG8gdCA9IEQtMTsgdCA+PSAwOyB0LS0pIHsKCQlpbnQgdG1wOwoJCWNpbiA+PiB0bXA7CgkJYXV0byB0cCA9IHRtcCA9PSAxOwoJCWlmICh0cCkgewoJCQlpbnQgdSwgdjsKCQkJY2luID4+IHUgPj4gdjsKCQkJdS0tOyB2LS07CgkJCWlmICh1ID4gdikgewoJCQkJc3dhcCh1LCB2KTsKCQkJfQoJCQlhdXRvIGUgPSBta0UodSwgdik7CgkJCWVzLmVyYXNlKGUpOwoJCQlkc3Uub3NbdF0gPSBPKHRwLCBlKTsKCQl9CgkJZWxzZSB7CgkJCWludCB1LCB4OwoJCQljaW4gPj4gdSA+PiB4OwoJCQl1LS07CgkJCWRzdS5zenNbdV0gLT0geDsKCQkJZHN1Lm9zW3RdID0gTyh0cCwgbWFrZV9wYWlyKHUsIHgpKTsKCQl9Cgl9Cglmb3IgKGF1dG8gZTogZXMpIHsKCQlkc3UudW5pKGZzdChlKSwgc25kKGUpKTsKCX0KCWRzdS5yZWMgPSB0cnVlOwoJcXMucmVzaXplKFMpOwoJZm9yIChhdXRvIGkgPSAwOyBpIDwgUzsgaSsrKSB7CgkJaW50IHUsIHY7CgkJY2luID4+IHUgPj4gdjsKCQl1LS07IHYtLTsKCQlsbCB0ZzsKCQljaW4gPj4gdGc7CgkJcXNbaV0gPSB7aSwge3UsIHZ9LCB0Z307Cgl9CglhbnMucmVzaXplKFMpOwoJYnNlYXJjaCgwLCBTLCAtMSwgRCsxKTsKCWZvciAoYXV0byBpID0gMDsgaSA8IFM7IGkrKykgewoJCXByaW50ZigiJWRcbiIsIEQtMS1hbnNbaV0pOwoJfQoJcmV0dXJuIDA7Cn0KIA==