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 <bits/stdc++.h>
using namespace std;
typedef bool boolean;

#define ll long long

const ll llf = (signed ll) (~0ull >> 3);

template <typename T>
void pfill(T* pst, const T* ped, T val) {
  for ( ; pst != ped; *(pst++) = val);
}

typedef class Edge {
  public:
    int ed, nx;
    ll r, c;

    Edge() {	}
    Edge(int ed, int nx, ll r, ll c) : ed(ed), nx(nx), r(r), c(c) {	}
} Edge;

typedef class MapManager {
  public:
    int* h;
    vector<Edge> es;

    MapManager() {	}
    MapManager(int n)  {
      h = new int[(n + 1)];
      memset(h, -1, (n + 1) << 2);
    }

    void add_edge(int u, int v, ll cap, ll c) {
      es.emplace_back(v, h[u], cap, c);
      h[u] = (signed) es.size() - 1;
    }
    void add_arc(int u, int v, ll cap, ll c) {
      add_edge(u, v, cap, c);
      add_edge(v, u, 0, -c);
    }
    Edge& operator [] (int p) {
      return es[p];
    }
} MapManager;

typedef class Data {
  public:
    ll f, c, res;

    Data(ll f, ll c, ll res) : f(f), c(c), res(res) { }
} Data;

typedef class Network {
  public:
    int S, T;
    MapManager g;

    Network() {	}
    Network(int S, int T) : S(S), T(T), g(T) {
      f = new ll[(T + 1)];
      mf = new ll[(T + 1)];
      le = new int[(T + 1)];
      vis = new boolean[T + 1];
    }

    ll *f, *mf;
    int *le;
    boolean *vis;

    void clear() {
      delete[] f;
      delete[] le;
      delete[] mf;
      delete[] vis;
    }

    vector<Data> conv;
    boolean spfa() {
      queue<int> Q;
      pfill(f, f + T + 1, llf);
      pfill(vis, vis + T + 1, false);
      Q.push(S);
      f[S] = 0, mf[S] = llf, le[S] = -1;
      while (!Q.empty()) {
        int e = Q.front();
        Q.pop();
        vis[e] = false;
        for (int i = g.h[e], eu; ~i; i = g[i].nx) {
          eu = g[i].ed;
          if (!g[i].r) continue;
          ll w = f[e] + g[i].c;
          if (w < f[eu]) {
            f[eu] = w, mf[eu] = min(mf[e], g[i].r), le[eu] = i;
            if (!vis[eu]) {
              Q.push(eu);
              vis[eu] = true;
            }
          }
        }
      }
      if (f[T] == llf)
        return false;
      ll flow = mf[T];
      for (int p = T, e; p ^ S; p = g[le[p] ^ 1].ed) {
        e = le[p];
        g[e].r -= flow;
        g[e ^ 1].r += flow;
      }
      Data t = conv.back();
      conv.emplace_back(t.f + flow, f[T], t.res + 1ll * f[T] * flow);
      if (t.f + flow >= (1ll << 50)) {
        return false;
      }
      return true;
    }

    void min_cost() {
      conv.emplace_back(0, 0, 0);
      while (spfa());
    }

    void add_edge(int u, int v, ll cap, ll w) {
      //			cerr << u << "->" << v << " " << cap << " " << w << '\n';
      g.add_arc(u, v, cap, w);		
    }
} Network;

typedef class Jewelry {
  public:
    int s, p;
    ll c;

    void read() {
      cin >> s >> p >> c;
    }
    boolean operator < (Jewelry b) const {
      return s < b.s;
    }
} Jewelry;

int n, m, q;
vector<vector<int>> id;
vector<vector<Jewelry>> shop;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  id.resize(n);
  shop.resize(n);
  int T = 0;
  for (int i = 0, K; i < n; i++) {
    cin >> K;
    id[i].resize(K - 1);
    shop[i].resize(K);
    for (auto& x : id[i]) {
      x = ++T;
    }
    id[i].push_back(-1);
    id[i].insert(id[i].begin(), 0);
    for (auto& x : shop[i]) {
      x.read();
    }
    sort(shop[i].begin(), shop[i].end());
  }
  Network network (0, ++T);
  for (auto& v : id) {
    v.back() = T;
  }
  for (int i = 0; i < n; i++) {
    int K = shop[i].size();
    for (int j = 0; j < K; j++) {
      network.add_edge(id[i][j], id[i][j + 1], shop[i][j].p, 0);
      network.add_edge(id[i][j + 1], id[i][j], llf, 0);
      network.add_edge(id[i][j], id[i][j + 1], llf, shop[i][j].c);
    }
  }
  cin >> m;
  for (int i = 0, x, y, w; i < m; i++) {
    cin >> x >> y >> w;
    --x, --y;
    int kx = shop[x].size(), ky = shop[y].size();
    for (int l = 0, r = 0; l < ky; l++) {
      while (r < kx && shop[y][l].s - w > shop[x][r].s) {
        r++;
      }
      network.add_edge(id[y][l], id[x][r], llf, 0);
    }
  }
  network.min_cost();
  auto& conv = network.conv;
  cin >> q;
  ll a;
  while (q--) {
    cin >> a;
    auto t = lower_bound(conv.begin(), conv.end(), a, [&] (Data x, ll y) {  return x.c < y; });
    if (t == conv.end()) {
      cout << "-1" << '\n';
    } else {
      --t;
      cout << 1ll * (*t).f * a - (*t).res << '\n'; 
    }
  }
  return 0;
}