Evil Chris Solution

#include<bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define endl '\n'

const int N=2e5+5;

int n,m,D,S;
int l[N],r[N],c[N],s[N],t[N],k[N],par[N],sum[N];
pair<int,pair<int,int>> a[N];
vector<int> mid[N];
set<pair<int,int>> ms;

int get_par(int x)
{
    while(x!=par[x])
    {
        par[x]=par[par[x]];
        x=par[x];
    }
    return x;
}

void merge(int u,int v)
{
    int p1=get_par(u);
    int p2=get_par(v);
    if(p1==p2)
    {
        return;
    }
    par[p2]=p1;
    sum[p1]+=sum[p2];
    sum[p2]=0;
}

void reset()
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        sum[i]=c[i];
    }
    for(auto &x:ms)
    {
        merge(x.ff,x.ss);
    }
}

void apply(int id)
{
    if(id==0)
    {
        return;
    }
    if(a[id].ff==1)
    {
        merge(a[id].ss.ff,a[id].ss.ss);
    }
    else
    {
        sum[get_par(a[id].ss.ff)]+=a[id].ss.ss;
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin>>n>>m>>D>>S;

    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
    }

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(u>v)
        {
            swap(u,v);
        }
        ms.insert({u,v});
    }

    for(int i=1;i<=D;i++)
    {
        cin>>a[i].ff>>a[i].ss.ff>>a[i].ss.ss;
        if(a[i].ff==1)
        {
            if(a[i].ss.ff>a[i].ss.ss)
            {
                swap(a[i].ss.ff,a[i].ss.ss);
            }
            ms.erase({a[i].ss.ff,a[i].ss.ss});
        }
        else
        {
            c[a[i].ss.ff]-=a[i].ss.ss;
        }
    }

    reverse(a+1,a+D+1);

    for(int i=1;i<=S;i++)
    {
        cin>>s[i]>>t[i]>>k[i];
        l[i]=0;
        r[i]=D+1;
    }

    bool done=0;
    while(!done)
    {
        done=1;
        reset();

        for(int i=1;i<=S;i++)
        {
            if(l[i]!=r[i])
            {
                done=0;
                int c_mid=(l[i]+r[i])>>1;
                mid[c_mid].push_back(i);
            }
        }

        for(int i=0;i<=D;i++)
        {
            apply(i);
            while(!mid[i].empty())
            {
                int id=mid[i].back();
                mid[i].pop_back();
                int p1=get_par(s[id]);
                int p2=get_par(t[id]);
                int have=sum[p1]+sum[p2];
                if(have>=k[id])
                {
                    r[id]=i;
                }
                else
                {
                    l[id]=i+1;
                }
            }
        }
    }

    for(int i=1;i<=S;i++)
    {
        assert(l[i]==r[i]);
        if(r[i]<=D)
        {
            cout<<D-r[i]<<endl;
        }
        else
        {
            cout<<-1<<endl;
        }
    }

}