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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define N 2333
typedef long long ll;
const ll inf=1LL<<50;
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,m,cnt[N],S,T,vis[N],id[33][33],tot,Q,e_cnt,head[N];
ll dis[N];
vector<pair<ll,ll> > vec,ans;
struct Jew{
	int s,p;
	ll c;
	bool operator <(const Jew b)const{
		return s<b.s;
	}
}a[33][33];
queue<int> q;
struct Edge{
	int to,nxt,val;
	ll cost;
}edge[N<<6];
void Add(int a,int b,int c,ll d){
	edge[++e_cnt]={b,head[a],c,d};
	head[a]=e_cnt;
}
void adde(int a,int b,int c,ll d){
	Add(a,b,c,d),Add(b,a,0,-d);
}
bool SPFA(){
	memset(dis,0x3f,sizeof(dis));
	dis[S]=0,vis[S]=1;
	q.push(S);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(edge[i].val&&dis[v]>dis[u]+edge[i].cost){
				dis[v]=dis[u]+edge[i].cost;
				if(!vis[v]){
					q.push(v),vis[v]=1;
				}
			}
		}
	}
	return dis[T]<inf;
}

int dfs(int u,int limit){
	if(u==T)return limit;
	int flow=0;
	vis[u]=1;
	for(int i=head[u];i&&limit;i=edge[i].nxt){
		int v=edge[i].to;
		if(edge[i].val&&dis[v]==dis[u]+edge[i].cost&&!vis[v]){
			int k=dfs(v,min(edge[i].val,limit));
			edge[i].val-=k;
			edge[i^1].val+=k;
			limit-=k;
			flow+=k;
		}
	}
	vis[u]=0;
	if(!flow)dis[u]=inf;
	return flow;
}
void Dinic(){
	int maxflow=0;
	while(SPFA()){
		maxflow=dfs(S,1e9);
		vec.emplace_back(dis[T],maxflow);
		if(maxflow>5e8)break;
	}
}
 int main(){
	n=read(),e_cnt=1,S=998,T=S+1;
	for(int i=1;i<=n;++i){
		cnt[i]=read();
		for(int j=1;j<=cnt[i];++j){
			a[i][j].s=read(),a[i][j].p=read(),a[i][j].c=read();
		}
		sort(a[i]+1,a[i]+cnt[i]+1);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=cnt[i]-1;++j){
			id[i][j]=++tot;
		}
		id[i][0]=S,id[i][cnt[i]]=T;
		for(int j=1;j<=cnt[i];++j){
			adde(id[i][j-1],id[i][j],a[i][j].p,0);
			adde(id[i][j-1],id[i][j],1e9,a[i][j].c);
		}
	}
	m=read();
	for(int i=1;i<=m;++i){
		int u=read(),v=read(),w=read();
		int k=1;
		for(int j=1;j<=cnt[v];++j){
			while(k<=cnt[u]&&a[u][k].s+w<a[v][j].s)++k;
			adde(id[v][j-1],id[u][k-1],1e9,0);
		}
	}
	Dinic();
	ll x=0,y=0;
	for(auto &t:vec){
		ans.emplace_back(x,y);
		x+=t.second;
		y+=t.first*t.second;
	}
	Q=read();
	while(Q--){
		ll A=read();
		int i=lower_bound(vec.begin(),vec.end(),make_pair(A,(ll)-inf))-vec.begin();
		printf("%lld\n",i==ans.size()?-1LL:ans[i].first*A-ans[i].second);
	}
	return 0;
}