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 ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
using namespace std;

const int N=55;
const int M=10005;
const int K=500005;
const ll inf=1ll<<60;
struct edge{
	int from,to,next;
	ll f,v;
}e[K];
int n,m,Q,SS,TT,nd,top;
int cnt[N],S[N][N],P[N][N],id[N][N];
int from[M],vis[M],q[M*50];
int head[M],tot=1;
ll C[N][N],dis[M],ans[K];
pll op[K],a[K];
void add(int x,int y,ll f,ll v){
	e[++tot]=(edge){x,y,head[x],f,v};
	head[x]=tot;
	e[++tot]=(edge){y,x,head[y],0,-v};
	head[y]=tot;
}
bool bfs(){
	For(i,1,nd) dis[i]=inf,vis[i]=0;
	int h=0,t=1; q[1]=SS; dis[SS]=0;
	while (h!=t){
		int x=q[++h]; vis[x]=0;
		for (int i=head[x];i;i=e[i].next)
			if (dis[e[i].to]>dis[x]+e[i].v&&e[i].f){
				dis[e[i].to]=dis[x]+e[i].v;
				from[e[i].to]=i;
				if (!vis[e[i].to]){
					vis[e[i].to]=1;
					q[++t]=e[i].to;
				}
			}
	}
	return dis[TT]!=inf;
}
void del(){
	ll f=inf;
	for (int i=from[TT];i;i=from[e[i].from])
		f=min(f,e[i].f);
	op[++top]=pll(f,dis[TT]);
	for (int i=from[TT];i;i=from[e[i].from])
		e[i].f-=f,e[i^1].f+=f;
}
int main(){
	#ifdef zyy
		freopen("1.in","r",stdin);
	#endif 
	scanf("%d",&n);
	For(i,1,n){
		scanf("%d",&cnt[i]);
		For(j,1,cnt[i]) scanf("%d%d%lld",&S[i][j],&P[i][j],&C[i][j]);
		For(j,1,cnt[i]) For(k,j+1,cnt[i])
			if (S[i][j]>S[i][k]){
				swap(S[i][j],S[i][k]);
				swap(P[i][j],P[i][k]);
				swap(C[i][j],C[i][k]);
			}
	}
	SS=++nd; TT=++nd;
	For(i,1,n){
		For(j,1,cnt[i]-1) id[i][j]=++nd;
		id[i][0]=SS; id[i][cnt[i]]=TT;
		For(j,1,cnt[i]){
			add(id[i][j],id[i][j-1],inf,0);
			add(id[i][j-1],id[i][j],inf,C[i][j]);
			add(id[i][j-1],id[i][j],P[i][j],0);
		}
	}
	scanf("%d",&m);
	For(i,1,m){
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		For(j,1,cnt[y]){
			int k=1;
			for (;k<=cnt[x]&&S[x][k]+c<S[y][j];++k);
			add(id[y][j-1],id[x][k-1],inf,0);
		}
	}
	for (;bfs();del());
	scanf("%d",&Q);
	For(i,1,Q) scanf("%lld",&a[i].fi);
	For(i,1,Q) a[i].se=i;
	sort(a+1,a+Q+1);
	int pos=1;
	ll slop=0;
	ll res=0;
	For(i,1,Q){
		res+=(a[i].fi-a[i-1].fi)*slop;
		for (;pos<=top&&op[pos].se<a[i].fi;++pos){
			slop+=op[pos].fi;
			res+=(a[i].fi-op[pos].se)*op[pos].fi;
		}
		//cout<<pos<<endl;
		if (slop>=1ll<<50)
			for (;i<=Q;i++) ans[a[i].se]=-1;
		else ans[a[i].se]=res;
	}
	For(i,1,Q)
		printf("%lld\n",ans[i]);
}
/*
min a[i] c[i]
a[i]-a[j]>=lim[ij]

id[i][j+1]-id[i][j]>=0
id[i][j]-id[i][j+1]>=-C[i][j]
id[vi][x]-id[ui][y]>=0

max -lim[ij] b[ij]
sum bij <=a[i]
*/