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>

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		static int num[40];
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (*num = 0; x; x /= 10) {
			num[++*num] = x % 10;
		}
		while (*num){
			putchar(num[*num] ^ '0');
			--*num;
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

struct Graph {
	const static int N = 905, M = 10005;
	const static int INF = 0x3f3f3f3f;
	const static long long INFll = 0x3f3f3f3f3f3f3f3fll;

	int n, S, T;
	int edge, to[M], pr[M], cap[M], hd[N];
	long long cost[M];

	void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T, edge = 0;
		for (int i = 0; i < n; ++i) {
			hd[i] = -1;
		}
	}

	void addEdge(int u, int v, int w, long long c) {
		// debug("EDGE %d %d %d %lld\n", u, v, w, c);
		to[edge] = v, cap[edge] = w, cost[edge] = c, pr[edge] = hd[u], hd[u] = edge++;
		to[edge] = u, cap[edge] = 0, cost[edge] = -c, pr[edge] = hd[v], hd[v] = edge++;
	}

	int pre[N];
	int mn[N];
	long long dis[N];

	bool SPFA() {
		static bool vis[N];
		for (int i = 0; i < n; ++i) {
			vis[i] = 0, dis[i] = INFll;
		}
		std::vector<int> Q;
		Q.push_back(S), vis[S] = 1, dis[S] = 0, mn[S] = INF;
		for (int k = 0; k < (int)Q.size(); ++k) {
			int u = Q[k];
			vis[u] = 0;
			for (int i = hd[u]; ~i; i = pr[i]) {
				int v = to[i];
				if (cap[i] && dis[v] > dis[u] + cost[i]) {
					dis[v] = dis[u] + cost[i];
					mn[v] = std::min(mn[u], cap[i]);
					pre[v] = i;
					if (!vis[v]) {
						Q.push_back(v);
						vis[v] = 1;
					}
				}
			}
		}
		return dis[T] < INFll;
	}

	std::vector<std::pair<long long, int>> MCMF() {
		std::vector<std::pair<long long, int>> res;
		while (SPFA()) {
			for (int u = T; u != S; u = to[pre[u] ^ 1]) {
				cap[pre[u]] -= mn[T], cap[pre[u] ^ 1] += mn[T];
			}
			res.push_back({dis[T], mn[T]});
			if (mn[T] > INF / 2) {
				break;
			}
		}
		return res;
	}
} G;

int n, K[35], cnt, id[35][35], m, Q;

struct Node {
	int S, P;
	long long C;

	bool operator < (const Node &rhs) const {
		return S < rhs.S;
	}
} a[35][35];

int main() {
	read(n);
	cnt = 2;
	for (int i = 1; i <= n; ++i) {
		read(K[i]);
		for (int j = 1; j <= K[i]; ++j) {
			read(a[i][j].S), read(a[i][j].P), read(a[i][j].C);
		}
		std::sort(a[i] + 1, a[i] + K[i] + 1);
		id[i][0] = 0, id[i][K[i]] = 1;
		for (int j = 1; j < K[i]; ++j) {
			id[i][j] = cnt++;
		}
	}
	G.init(cnt, 0, 1);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= K[i]; ++j) {
			G.addEdge(id[i][j - 1], id[i][j], a[i][j].P, 0);
			G.addEdge(id[i][j - 1], id[i][j], G.INF, a[i][j].C);
		}
	}
	read(m);
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		read(u), read(v), read(w);
		for (int j = 1; j <= K[v]; ++j) {
			int k = std::lower_bound(a[u] + 1, a[u] + 1 + K[u], (Node){a[v][j].S - w, 0, 0}) - a[u];
			G.addEdge(id[v][j - 1], id[u][k - 1], G.INF, 0);
		}
	}
	std::vector<std::pair<long long, int>> p = G.MCMF();
	std::vector<std::pair<int, long long>> q;
	int x = 0;
	long long y = 0;
	for (auto v : p) {
		q.push_back({x, y});
		x += v.second, y += v.first * v.second;
	}
	read(Q);
	while (Q--) {
		long long A;
		read(A);
		int pos = std::lower_bound(p.begin(), p.end(), std::make_pair(A, -G.INF)) - p.begin();
		if (pos == (int)p.size()) {
			print(-1);
		} else {
			print(q[pos].first * A - q[pos].second);
		}
	}
}