Problem: There are N jewelry shops numbered 1 to N.

Shop i (1 \leq i \leq N) sells K_i kinds of jewels. The j-th of these jewels (1 \leq j \leq K_i) has a size and price of S_{i,j} and P_{i,j}, respectively, and the shop has C_{i,j} jewels of this kind in stock.

A jewelry box is said to be good if it satisfies all of the following conditions:

* For each of the jewelry shops, the box contains one jewel purchased there.
* All of the following M restrictions are met.
* Restriction i (1 \leq i \leq M): (The size of the jewel purchased at Shop V_i)\leq (The size of the jewel purchased at Shop U_i)+W_i



Answer Q questions. In the i-th question, given an integer A_i, find the minimum total price of jewels that need to be purchased to make A_i good jewelry boxes. If it is impossible to make A_i good jewelry boxes, report that fact.

Constraints

* 1 \leq N \leq 30
* 1 \leq K_i \leq 30
* 1 \leq S_{i,j} \leq 10^9
* 1 \leq P_{i,j} \leq 30
* 1 \leq C_{i,j} \leq 10^{12}
* 0 \leq M \leq 50
* 1 \leq U_i,V_i \leq N
* U_i \neq V_i
* 0 \leq W_i \leq 10^9
* 1 \leq Q \leq 10^5
* 1 \leq A_i \leq 3 \times 10^{13}
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
Description of Shop 1
Description of Shop 2
\vdots
Description of Shop N
M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
Q
A_1
A_2
\vdots
A_Q


The description of Shop i (1 \leq i \leq N) is in the following format:


K_i
S_{i,1} P_{i,1} C_{i,1}
S_{i,2} P_{i,2} C_{i,2}
\vdots
S_{i,K_i} P_{i,K_i} C_{i,K_i}


Output

Print Q lines. The i-th line should contain the minimum total price of jewels that need to be purchased to make A_i good jewelry boxes, or -1 if it is impossible to make them.

Examples

Input

3
2
1 10 1
3 1 1
3
1 10 1
2 1 1
3 10 1
2
1 1 1
3 10 1
2
1 2 0
2 3 0
3
1
2
3


Output

3
42
-1


Input

5
5
86849520 30 272477201869
968023357 28 539131386006
478355090 8 194500792721
298572419 6 894877901270
203794105 25 594579473837
5
730211794 22 225797976416
842538552 9 420531931830
871332982 26 81253086754
553846923 29 89734736118
731788040 13 241088716205
5
903534485 22 140045153776
187101906 8 145639722124
513502442 9 227445343895
499446330 6 719254728400
564106748 20 333423097859
5
332809289 8 640911722470
969492694 21 937931959818
207959501 11 217019915462
726936503 12 382527525674
887971218 17 552919286358
5
444983655 13 487875689585
855863581 6 625608576077
885012925 10 105520979776
980933856 1 711474069172
653022356 19 977887412815
10
1 2 231274893
2 3 829836076
3 4 745221482
4 5 935448462
5 1 819308546
3 5 815839350
5 3 513188748
3 1 968283437
2 3 202352515
4 3 292999238
10
510266667947
252899314976
510266667948
374155726828
628866122125
628866122123
1
628866122124
510266667949
30000000000000


Output

26533866733244
13150764378752
26533866733296
19456097795056
-1
33175436167096
52
33175436167152
26533866733352
-1

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include <tuple>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

template<class C, class D, class E>
struct MinCostFlow {
    static constexpr D INF = numeric_limits<D>::max();
    int n;
    VV<E> g;
    int s, t;
    C nc, cap_flow = 0;
    D nd, flow = 0;

    V<D> dual;
    V<int> pv, pe;

    MinCostFlow(VV<E> _g, int _s, int _t, bool neg)
        : n(int(_g.size())), g(_g), s(_s), t(_t) {
        assert(s != t);
        dual = V<D>(n);
        pv = pe = V<int>(n);
        if (neg) {
            V<D> dist(n, D(INF));
            dist[s] = 0;
            for (int ph = 0; ph < n; ph++) {
                bool update = false;
                for (int i = 0; i < n; i++) {
                    if (dist[i] == INF) continue;
                    for (auto e: g[i]) {
                        if (!e.cap) continue;
                        if (dist[i] + e.dist < dist[e.to]) {
                            dist[e.to] = dist[i] + e.dist;
                            update = true;
                        }
                    }
                }
                if (!update) break;
            }
            for (int v = 0; v < n; v++) {
                dual[v] += dist[v];
            }
        }
        dual_ref();
    }

    C single_flow(C c) {
        if (nd == INF) return nc;
        c = min(c, nc);
        for (int v = t; v != s; v = pv[v]) {
            E& e = g[pv[v]][pe[v]];
            e.cap -= c;
            g[v][e.rev].cap += c;
        }
        cap_flow += c;
        flow += nd * c;
        nc -= c;
        if (!nc) dual_ref();
        return c;
    }

    void max_flow(C c) {
        while (c) {
            C f = single_flow(c);
            if (!f) break;
            c -= f;
        }
    }

    void dual_ref() {
        V<D> dist(g.size(), D(INF));
        pv = pe = V<int>(n, -1);
        struct Q {
            D key;
            int to;
            bool operator<(Q r) const { return key > r.key; }
        };
        priority_queue<Q> que;
        dist[s] = 0;
        que.push(Q{D(0), s});
        V<char> vis(n);
        while (!que.empty()) {
            int v = que.top().to; que.pop();
            if (v == t) break;
            if (vis[v]) continue;
            vis[v] = true;
            for (int i = 0; i < int(g[v].size()); i++) {
                E e = g[v][i];
                if (vis[e.to] || !e.cap) continue;
                D cost = dist[v] + e.dist + dual[v] - dual[e.to];
                if (dist[e.to] > cost) {
                    dist[e.to] = cost;
                    pv[e.to] = v; pe[e.to] = i;
                    que.push(Q{dist[e.to], e.to});
                }
            }
        }
        if (dist[t] == INF) {
            nd = INF; nc = 0;
            return;
        }
        for (int v = 0; v < n; v++) {
            if (!vis[v]) continue;
            dual[v] += dist[v] - dist[t];
        }
        nd = dual[t] - dual[s];
        nc = numeric_limits<C>::max();
        for (int v = t; v != s; v = pv[v]) {
            nc = min(nc, g[pv[v]][pe[v]].cap);
        }
    }
};

template<class C, class D, class E>
MinCostFlow<C, D, E> get_mcf(const VV<E>& g, int s, int t, bool neg = false) {
    return MinCostFlow<C, D, E>(g, s, t, neg);
}

int main() {
    int n;
    cin >> n;
    struct Stone {
        ll size, num;
        int cost;
    };
    V<int> offset(n + 1);
    VV<Stone> stones(n);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        offset[i + 1] = offset[i] + k;
        stones[i] = V<Stone>(k);
        for (int j = 0; j < k; j++) {
            cin >> stones[i][j].size >> stones[i][j].cost >> stones[i][j].num;            
        }
        sort(stones[i].begin(), stones[i].end(), [&](const Stone& l, const Stone& r) {
            return l.size < r.size;
        });  
    }
    int sv = offset[n], tv = sv + 1;

    struct E {
        int to, rev, cap; ll dist;
    };
    VV<E> g(tv + 1);
    auto add_edge = [&](int from, int to, int cap, ll dist) {
        g[from].push_back(E{to, int(g[to].size()), cap, dist});
        g[to].push_back(E{from, int(g[from].size())-1, 0, -dist});
    };

    const int INF_CAP = int(TEN(9));
    for (int i = 0; i < n; i++) {
        int k = int(stones[i].size());
        int bk = sv;
        for (int j = 0; j < k; j++) {
            // x_ij >= x_i{j-1}
            int nw = offset[i] + j;
            add_edge(nw, bk, INF_CAP, 0);
            add_edge(bk, nw, INF_CAP, stones[i][j].num);
            add_edge(bk, nw, stones[i][j].cost, 0);
            bk = nw;
        }
        add_edge(bk, tv, INF_CAP, 0);
        add_edge(tv, bk, INF_CAP, 0);
    }

    int m;
    cin >> m;
    for (int ph = 0; ph < m; ph++) {
        int u, v; ll w;
        cin >> u >> v >> w; u--; v--;
        int ku = int(stones[u].size());
        int kv = int(stones[v].size());
        for (int i = 0; i < ku; i++) {
            for (int j = 0; j < kv; j++) {
                if (stones[u][i].size + w < stones[v][j].size) {
                    // x_ui <= x_v(j-1)
                    int vjn1 = (j == 0 ? sv : offset[v] + j - 1);
                    add_edge(vjn1, offset[u] + i, INF_CAP, 0);
                    break;
                }
            }
        }
    }

    auto res = get_mcf<int, ll>(g, sv, tv, false);
    using Line = tuple<ll, int, ll>;
    V<Line> lines;
    while (true) {
        lines.push_back(Line{res.nd, res.cap_flow, res.flow});
//        cerr << res.nc << " " << res.nd << endl;
        if (INF_CAP / 2 < res.nc) break;
        res.single_flow(res.nc);        
    }
    //res.max_flow(TEN(9));

    int q;
    cin >> q;
    for (int ph = 0; ph < q; ph++) {
        ll a;
        scanf("%lld", &a);
        auto it = lower_bound(lines.begin(), lines.end(), Line{a, -1, -1});
        if (it == lines.end()) {
            printf("-1\n");
            continue;
        }
        int cap_flow;
        ll flow;
        tie(ignore, cap_flow, flow) = *it;
        ll sum = cap_flow * a - flow;
        printf("%lld\n", sum);
    }
    return 0;
}