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

typedef long long ll;
typedef pair<int, int> pii;
const ll Val = 1000000;

int pL[605], pR[605];
int L[605], R[605], fa[605], siz[605], U[2005], V[2005], W[2005];
inline int findfa(int x) { return x == fa[x] ? x : fa[x] = findfa(fa[x]); }
inline void merge(int u, int v) { u = findfa(u), v = findfa(v); if (u == v) return; if (u < v) swap(u, v); fa[u] = v; siz[v] += siz[u]; }

vector<pii> g[605], E;
int cnt[7], sum[605], bel[605], col[605];
int X[605], Y[605], id[605], rk[605], dt, n, ln;
bool ban[605][2];

namespace Maxflow
{
    const int maxn = 2010;
    const int maxm = 10005;
    const ll INF = 1e18;

    int s, t;
    struct edge
    {
        int v, next;
        ll flow;
    }e[maxm << 1];
    int head[maxn], tot;

    inline void addedge(int u, int v, ll c)
    {
        e[++tot] = (edge){v, head[u], c}; head[u] = tot;
        e[++tot] = (edge){u, head[v], 0}; head[v] = tot;
    }

    int d[maxn], cur[maxn];
    bool vis[maxn];
    bool bfs()
    {
        for (int i = s; i <= t; i++) d[i] = 0, cur[i] = head[i];
        queue<int> q;
        q.push(s), d[s] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = e[i].next)
            {
                int v = e[i].v;
                if (!d[v] && e[i].flow)
                {
                    d[v] = d[u] + 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    ll dfs(int u, ll flow)
    {
        if (u == t || !flow) return flow;
        ll rest = flow;
        for (int i = cur[u]; ~i; i = e[i].next)
        {
            int v = e[i].v;
            if (d[v] == d[u] + 1 && e[i].flow)
            {
                ll k = dfs(v, min(rest, e[i].flow));
                if (!k) d[v] = 0;
                e[i].flow -= k;
                e[i ^ 1].flow += k;
                rest -= k;
                if (!rest) break;
            }
            cur[u] = i;
        }
        return flow - rest;
    }

    ll Dinic()
    {
        ll maxflow = 0;
        while (bfs())
        {
            ll flow = 0;
            while (flow = dfs(s, INF)) maxflow += flow;
        }
        return maxflow;
    }
}

void Solve(int d1, int d2)
{
    using namespace Maxflow;
    for (int i = 0; i <= ln * 2 + 1; i++) head[i] = -1, vis[i] = 0; tot = -1;
    s = 0, t = ln * 2 + 1;
    int A = X[d1] - X[d2], B = Y[d2] - Y[d1];
    for (int i = 1; i <= n; i++)
        if (!col[i])
        {
            if (!ban[i][0]) addedge(s, id[i], B * sum[i]);
            if (!ban[i][1]) addedge(id[i] + ln, t, A * sum[i]);
            addedge(id[i], id[i] + ln, INF);
        }
    for (auto [u, v] : E) addedge(u, v + ln, INF);
    Dinic(); int C = 0, D = 0;
    for (int i = 1; i <= ln; i++)
        if (d[i] && !ban[rk[i]][0]) C += sum[rk[i]];
        else if (!d[i + ln] && !ban[rk[i]][1]) D += sum[rk[i]];
    // cout << C << " " << D << " " << A << " " << B << "\n";
    if ((C - X[d2]) * (D - Y[d1]) <= (X[d1] - C) * (Y[d2] - D)) return;
    X[++dt] = C, Y[dt] = D; int nw = dt;
    Solve(d1, nw), Solve(nw, d2);
}

int totq;
void work()
{
    int k, m, q;
    cin >> k >> n >> m >> q; E.clear();
    for (int i = 1; i <= n; i++)
    {
        cin >> pL[i] >> pR[i];
        fa[i] = i, siz[i] = 1, col[i] = bel[i] = 0;
        ban[i][0] = ban[i][1] = 0;
        g[i].clear();
    }
    for (int i = 1; i <= 5; i++) cnt[i] = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> U[i] >> V[i] >> W[i];
        if (!W[i]) merge(U[i], V[i]);
    }

    int tn = 0, all = n;
    for (int i = 1; i <= n; i++)
        if (i == findfa(i))
        {
            sum[++tn] = siz[i];
            int nl = 0, nr = n;
            for (int j = 1; j <= n; j++)
                if (findfa(j) == i)
                {
                    bel[j] = tn;
                    nl = max(nl, pL[j]), nr = min(nr, pR[j]);
                }
            L[tn] = nl, R[tn] = nr;
        }
    n = tn;
    
    for (int i = 1; i <= m; i++)
        if (W[i] <= 2)
        {
            g[bel[U[i]]].emplace_back(make_pair(bel[V[i]], W[i]));
            g[bel[V[i]]].emplace_back(make_pair(bel[U[i]], W[i]));
        }

    for (int i = 1; i <= n; i++)
        if (L[i] == R[i]) cnt[L[i]] += sum[i], col[i] = L[i];

    for (int i = 1; i <= n; i++)
    {
        if (col[i]) continue;
        if (R[i] <= 2) col[i] = 2, cnt[2] += sum[i];
        else if (R[i] <= 3) ban[i][1] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        if (col[i]) continue;
        if (L[i] >= 4) col[i] = 4, cnt[4] += sum[i];
        else if (L[i] >= 3) ban[i][0] = 1;
    }

    for (int i = 1; i <= n; i++)
        if (col[i] == 1)
        {
            for (auto [v, w] : g[i])
            {
                if (col[v]) continue;
                if (w == 1) col[v] = 2, cnt[2] += sum[v];
                else if (w == 2) ban[v][1] = 1;
            }
        }
        else if (col[i] == 5)
        {
            for (auto [v, w] : g[i])
            {
                if (col[v]) continue;
                if (w == 1) col[v] = 4, cnt[4] += sum[v];
                else if (w == 2) ban[v][0] = 1;
            }
        }
    for (int i = 1; i <= n; i++)
        if (col[i] == 2 || col[i] == 4)
        {
            for (auto [v, w] : g[i])
                if (!col[v] && w == 1) ban[v][(col[i] == 2)] = 1;
        }
    
    ln = 0;
    for (int u = 1; u <= n; u++)
        if (!col[u]) id[u] = ++ln, rk[ln] = u;
    for (int u = 1; u <= n; u++)
        for (auto [v, w] : g[u])
            if (!col[u] && !col[v] && w == 1) E.emplace_back(make_pair(id[u], id[v]));
    int mx2 = 0, mx4 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!col[i] && !ban[i][0]) mx2 += sum[i];
        if (!col[i] && !ban[i][1]) mx4 += sum[i];
    }
    X[1] = mx2, Y[1] = 0;
    X[2] = 0, Y[2] = mx4; dt = 2;
    Solve(1, 2);
    // for (int i = 1; i <= dt; i++) cout << "D " << X[i] << " " << Y[i] << "\n";
    
    int sum234 = all - cnt[1] - cnt[5];
    ll ansC = Val * (cnt[1] * cnt[1] + sum234 * sum234 + cnt[5] * cnt[5]) + Val * 2 * (cnt[1] * cnt[2] + cnt[4] * cnt[5] - cnt[2] * cnt[4]);
    while (q--)
    {
        ll v1 = 0, v2 = 0, v3 = 0;
        cin >> v1; if (k >= 4) cin >> v2; if (k >= 5) cin >> v3;
        ll ans = ansC + v2 * sum234 + (v1 - v2) * cnt[2] + (v3 - v2) * cnt[4];
        ll a = Val * 2 * (cnt[1] - cnt[4]) + v1 - v2, b = Val * 2 * (cnt[5] - cnt[2]) + v3 - v2, res = 0;
        for (int i = 1; i <= dt; i++) res = max(res, -Val * 2 * X[i] * Y[i] + a * X[i] + b * Y[i]);
        cout << res + ans << "\n";
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);

    int cid, T; cin >> cid >> T;
    while (T--) work();
    return 0;
}