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;
int n,m;

const int N = 10010, M = 100010;
typedef long long ll;
const ll INF = 1e18;
typedef pair<ll,ll> pll;
vector<pll> P;
int all=2,src=1,t=2;
namespace graph{
	int S,T,cnt=1,hed[N],to[M],nxt[M];
	ll cap[M],cost[M];
	inline void adde(int u,int v,ll _fl,ll _c){
		++cnt;to[cnt]=v,nxt[cnt]=hed[u],cap[cnt]=_fl,cost[cnt]=_c;hed[u]=cnt;
		++cnt;to[cnt]=u,nxt[cnt]=hed[v],cap[cnt]=0,cost[cnt]=-_c;hed[v]=cnt;
	}

	queue<int>Q;
	ll d[N];bool vis[N];ll incf[N];
	int pre[N];
	bool spfa(){
		for(int i=min(1,S);i<=max(all,T);i++)d[i]=INF;
		memset(vis,0,sizeof(vis));
		Q.push(S);d[S]=0;vis[S]=1;
		incf[S]=INF;
		while(!Q.empty()){
			// cout << Q.front() << "?" << endl;
			int u=Q.front();vis[u]=false;Q.pop();
			// cout << u << " " << endl;
			for(int i=hed[u];i;i=nxt[i]){
				int v=to[i];
				if(!cap[i])continue;
				if(d[v]>d[u]+cost[i]){
					d[v]=d[u]+cost[i];
					incf[v]=min(incf[u],cap[i]);
					pre[v]=i;
					if(!vis[v])vis[v]=true,Q.push(v);
				}
			}
		}
		if(d[T]==INF)return false;
		return true;
	}
	ll mincost,maxflow;
	void update(){
		int x=T;
		while(x!=S){
			int i=pre[x];
			cap[i]-=incf[T];
			cap[i^1]+=incf[T];
			x=to[i^1];
		}
		maxflow+=incf[T];
		mincost+=d[T]*incf[T];
		P.push_back(pll(d[T],incf[T]));
	}

	void mincost_maxflow(){
		while(spfa()){
			// cout << ":" << endl;
			update();
			// cout << "!" << endl;
			if(P.back().second>(1ll<<50))break;
		}
	}
}

const int NN = 110;
int id[NN][NN], cnt[NN];
int s[NN][NN], p[NN][NN];
ll c[NN][NN];

int main()
{
	cin >> n;
	for(int i=1;i<=n;i++){
		scanf("%d",&cnt[i]);
		for(int j=1;j<=cnt[i];j++){
			scanf("%d%d%lld",&s[i][j],&p[i][j],&c[i][j]);
		}
		for(int j=1;j<=cnt[i];j++)for(int k=j+1;k<=cnt[i];k++){
			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]);
			}
		}
	}
	graph::S=src,graph::T=t;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt[i]-1;j++){
			id[i][j]=++all;
		}
		id[i][0]=src, id[i][cnt[i]]=t;
		for(int j=1;j<=cnt[i];j++){
			graph::adde(id[i][j-1],id[i][j],p[i][j],0);
			graph::adde(id[i][j-1],id[i][j],INF,c[i][j]);
		}
	}cin >> m;
	while(m--){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		for(int j=1,k=1;j<=cnt[v];j++){
			for(;k<=cnt[u]&&s[u][k]+w<s[v][j];++k);
			graph::adde(id[v][j-1],id[u][k-1],INF,0);
		}
	}
	// cout << " --- " << endl;
	graph::mincost_maxflow();
	vector<pll> q;
	ll x=0,y=0;
	for(size_t i=0;i<P.size();i++){
		// cout << P[i].first << " " << P[i].second << endl;
		q.push_back(pll(x,y));
		x+=P[i].second,y+=P[i].first*P[i].second;
	}
	cin >> m;
	while(m--){
		ll A;scanf("%lld",&A);
		size_t i=lower_bound(P.begin(),P.end(),pll(A,-INF))-P.begin();
		if(i==P.size())printf("-1\n");
		else printf("%lld\n",q[i].first*A-q[i].second);
	}
}