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<cstdio>
#include<queue>
#include<algorithm>
typedef long long ll;
const int inf=1e9;
int N,K[33],M,U[55],V[55],W[55];
struct Jewel{int S,P;ll C;bool operator<(const Jewel&j)const{return S<j.S;}}J[33][33];
int no(int i,int j){return j?j<K[i]?2+i+(j-1)*N:1:0;}
struct Edge{int to,cap;ll cost;Edge*rev,*next;}E[33333],*ne=E,*fir[999];
void link(int a,int b,int c,int cr,ll cost){
	*ne=(Edge){b,c,cost,ne+1,fir[a]};fir[a]=ne++;
	*ne=(Edge){a,cr,-cost,ne-1,fir[b]};fir[b]=ne++;
}
ll D[999],h[999];
bool vis[999];
Edge*fr[999];
struct Item{int v;ll d;Edge*e;bool operator<(const Item&it)const{return d>it.d;}};
void sp(){
	std::priority_queue<Item>Q;
	Q.push((Item){0,0,0});
	for(int i=0;i<N;i++)
		for(int j=0;j<=K[i];j++)h[no(i,j)]=D[no(i,j)],vis[no(i,j)]=0;
	while(!Q.empty()){
		Item it=Q.top();Q.pop();
		if(vis[it.v])continue;
		vis[it.v]=1;D[it.v]=it.d+h[it.v];fr[it.v]=it.e;
		for(Edge*e=fir[it.v];e;e=e->next)if(e->cap&&!vis[e->to])Q.push((Item){e->to,D[it.v]+e->cost-h[e->to],e});
	}
}
int cnt,X[111111];
ll Y[111111],kr[111111];
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",K+i);
		for(int j=0;j<K[i];j++)
			scanf("%d%d%lld",&J[i][j].S,&J[i][j].P,&J[i][j].C);
		std::sort(J[i],J[i]+K[i]);
		for(int j=0;j<K[i];j++){
			link(no(i,j),no(i,j+1),J[i][j].P,inf,0);
			link(no(i,j),no(i,j+1),inf,0,J[i][j].C);
		}
	}
	scanf("%d",&M);
	for(int i=0;i<M;i++){
		scanf("%d%d%d",U+i,V+i,W+i);
		--U[i];--V[i];
		for(int j=0,k=0;j<K[V[i]];j++){
			while(k<K[U[i]]&&J[V[i]][j].S>J[U[i]][k].S+W[i])k++;
			if(k)link(no(V[i],j),no(U[i],k),inf,0,0);
		}
	}
	int c=0;ll f=0;
	for(;;){
		sp();
		int mc=inf;
		for(int v=1;v;v=fr[v]->rev->to)
			if(fr[v]->cap<mc)mc=fr[v]->cap;
		kr[cnt]=D[1];X[cnt]=c;Y[cnt++]=f;
		if(mc>inf/2)break;
		c+=mc;f+=1ll*mc*D[1];
		for(int v=1;v;v=fr[v]->rev->to)
			fr[v]->cap-=mc,fr[v]->rev->cap+=mc;
	}
	int Q;scanf("%d",&Q);
	while(Q--){
		ll A;scanf("%lld",&A);
		int i=std::lower_bound(kr,kr+cnt,A)-kr;
		printf("%lld\n",i<cnt?X[i]*A-Y[i]:-1ll);
	}
}