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;
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
struct Shop {
	int s, p;
	ll c;
};
int mp[35][35];
struct Mcmf {
	const ll INFC = 1LL << 60;
	struct Edge {
		int to;
		int f, cap;
		ll cost;
	};
	int n, src, sink;
	vector<ll> pi, dist;
	vector<int> fromEdge;
	vector<Edge> edges;
	vector<vector<int>> G;
	Mcmf(int _n, int _src = -1, int _sink = -1) : n(_n), src(_src), sink(_sink) {
		G.resize(n);
		dist.resize(n);
		pi.resize(n);
		fromEdge.resize(n);
	}
	void addEdge(int from, int to, int cap, ll cost) {
		G[from].push_back(edges.size());
		edges.push_back({to, 0, cap, cost});
		G[to].push_back(edges.size());
		edges.push_back({from, 0, 0, -cost});
	}
	ll cheapestPath() {
		typedef pair<ll, int> Pair;
		priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
		fill(dist.begin(), dist.begin() + n, INFC);
		dist[src] = 0;
		pq.emplace(dist[src], src);
		while (!pq.empty()) {
			int u = pq.top().second;
			ll cdist = pq.top().first;
			pq.pop();
			if (cdist > dist[u]) continue;
			for (int x : G[u]) {
				Edge e = edges[x];
				if (e.f == e.cap) continue;
				int v = e.to;
				// assert pi[u], pi[v] <<< INFC
				ll val = dist[u] + pi[u] - pi[v] + e.cost;
				if (val < dist[v]) {
					dist[v] = val;
					fromEdge[v] = x;
					pq.emplace(dist[v], v);
				}
			}
		}
		if (dist[sink] >= INFC) return INFC;
		ll cost = dist[sink] + pi[sink];
		for (int k = 0; k < n; ++k)
			pi[k] = min(INFC, pi[k] + dist[k]);
		return cost;
	}
	vector<ll> maxFlow() {
		vector<ll> ret(1, 0);
		int totflow = 0;
		const int LIM = 27905;
		while (totflow < LIM) {
			ll cost = cheapestPath();
			// Change INFC to 0 to find min-cost flow (not maxflow)
			// Can prove that marginal-cost of flows increases (by exchange)
			if (cost >= INFC) break;
			int flow = INT_MAX;
			for (int x = sink; x != src;) {
				int e = fromEdge[x];
				flow = min(flow, edges[e].cap - edges[e].f);
				x = edges[e ^ 1].to;
			}
			for (int x = sink; x != src;) {
				int e = fromEdge[x];
				edges[e].f += flow;
				edges[e ^ 1].f -= flow;
				x = edges[e ^ 1].to;
			}
			flow = min(flow, LIM - totflow);
			totflow += flow;
			// Inc one flow at a time
			for (int i = 0; i < flow; ++i) {
				ret.push_back(cost);
			}
		}
		return ret;
	}
	// pi makes all edges nonnegative, so initialize if necessary
	void initPi() {
		fill(pi.begin(), pi.begin() + n, 0);
	}
};
int main() {
	int n;
	scanf("%d", &n);
	vector<vector<Shop>> shops(n);
	vector<vector<int>> shopSizes(n);
	int vars = 0;	
	for (int i = 0; i < n; ++i) {
		int k;
		scanf("%d", &k);
		shops[i].resize(k);
		for (int j = 0; j < k; ++j) {
			Shop& s = shops[i][j];
			scanf("%d%d%lld", &s.s, &s.p, &s.c);
			mp[i][j] = vars++;
		}
		mp[i][k] = vars++;
		sort(shops[i].begin(), shops[i].end(), [](Shop a, Shop b) {
			return a.s < b.s;
		});
		for (Shop& s : shops[i]) shopSizes[i].push_back(s.s);
	}
	auto var = [&](int a, int b) {
		return mp[a][b];
	};
	int m;
	scanf("%d", &m);
	vector<pair<pair<int, int>, pair<int, int>>> constraints;
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		--u;
		--v;
		for (int j = 0; j < shops[v].size(); ++j) {
			int s = shops[v][j].s;
			int k = lower_bound(shopSizes[u].begin(), shopSizes[u].end(), s - w) - shopSizes[u].begin();
			// x(u, k) <= x(v, j)
			constraints.emplace_back(make_pair(u, k), make_pair(v, j));
		}
	}
	const int CAP = 1e8;
	Mcmf g(vars + 2, vars, vars + 1);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < shops[i].size(); ++j) {
			g.addEdge(var(i, j + 1), var(i, j), CAP, 0);
			g.addEdge(var(i, j), var(i, j + 1), CAP, shops[i][j].c);
			g.addEdge(var(i, j), var(i, j + 1), shops[i][j].p, 0);
//			int res = -shops[i][j].p;
//			if (j) res += shops[i][j - 1].p;
//			if (res < 0) g.addEdge(var(i, j), var(i, j + 1), -res, 0);
		}
		g.addEdge(g.src, var(i, 0), CAP, 0);
		g.addEdge(var(i, shops[i].size()), g.sink, CAP, 0);
	}
	for (auto& c : constraints) {
		g.addEdge(var(c.second.first, c.second.second), var(c.first.first, c.first.second), CAP, 0);
	}
	auto costs = g.maxFlow();
	vector<ll> pcost(costs.size() + 1);
	for (int i = 0; i < costs.size(); ++i) {
		pcost[i + 1] = pcost[i] + costs[i];
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		ll qa;
		scanf("%lld", &qa);
		int i = lower_bound(costs.begin(), costs.end(), qa) - costs.begin();
		if (i == costs.size()) printf("-1\n");
		else {
			ll ans = qa * (i - 1) - pcost[i];
			assert(ans >= 0);
			printf("%lld\n", ans);
		}
	}
	return 0;
}