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 re register
#define cs const

namespace IO{
	inline char gc(){
		static cs int Rlen=1<<22|1;static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; 
	}template<typename T>T get_integer(){
		char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48;
		while(isdigit(c=gc()))x=((x+(x<<2))<<1)+(c^48);return f?-x:x;
	}inline int gi(){return get_integer<int>();}
	inline ll gl(){return get_integer<ll>();}
}using namespace IO;

using std::cerr;
using std::cout;
using pll=std::pair<ll,ll>;
#define fi first
#define se second

cs ll INF=1ll<<60;

int Src,Snk,ct;

namespace NetWork{

cs int N=1e3+7;

struct edge{int to,rev;ll cap,w;};
typedef std::vector<edge>::iterator iter;
std::vector<edge> G[N];iter cur[N];
inline void adde(int u,int v,ll cap,ll cost){
	G[u].push_back({v,(int)G[v].size(),cap,cost});
	G[v].push_back({u,(int)G[u].size()-1,0,-cost});
}

ll dis[N];bool vs[N];

bool SPFA(){
	memset(dis,0x3f,sizeof dis);
	memset(vs,0,sizeof vs);
	std::deque<int> q({Src});dis[Src]=0;
	while(!q.empty()){
		int u=q.front();q.pop_front();
		vs[u]=false;cur[u]=G[u].begin();
		for(cs edge &e:G[u])
		if(e.cap&&dis[e.to]>dis[u]+e.w){
			dis[e.to]=dis[u]+e.w;
			if(!vs[e.to]){
				if(!q.empty()&&dis[e.to]<dis[q.front()])
					q.push_front(e.to);
				else q.push_back(e.to);
				vs[e.to]=true;
			}
		}
	}return dis[Snk]<INF;
}

ll tot_flow,tot_cost;
ll dfs(int u,ll flow){
	if(u==Snk){tot_flow+=flow;return flow;}
	ll ans=0;vs[u]=true;
	for(iter &e=cur[u];e!=G[u].end();++e)
	if(e->cap&&dis[e->to]==dis[u]+e->w&&!vs[e->to]){
		ll dlt=dfs(e->to,std::min(flow-ans,e->cap));
		e->cap-=dlt;G[e->to][e->rev].cap+=dlt;
		vs[e->to]=dlt==0;if((ans+=dlt)==flow)break;
	}vs[u]=false;return ans;
}

std::vector<pll> Flow(){
	std::vector<pll> p;
	while(SPFA()){
		tot_flow=0;dfs(Src,INF);
		p.push_back({dis[Snk],tot_flow});
		if(tot_flow>(1ll<<50))break;
	}return p;
}

}

cs int N=35;
int id[N][N],cnt[N];
int S[N][N],P[N][N];
ll C[N][N];

void Main(){
	int n=gi();
	for(int re i=1;i<=n;++i){
		cnt[i]=gi();
		for(int re j=1;j<=cnt[i];++j)
			S[i][j]=gi(),P[i][j]=gi(),C[i][j]=gl();
		for(int re j=1;j<=cnt[i];++j)
			for(int re k=j+1;k<=cnt[i];++k)
			if(S[i][j]>S[i][k]){
				std::swap(S[i][j],S[i][k]);
				std::swap(P[i][j],P[i][k]);
				std::swap(C[i][j],C[i][k]);
			}
	}Src=0,Snk=ct=1;
	for(int re i=1;i<=n;++i){
		for(int re j=1;j<=cnt[i]-1;++j)
			id[i][j]=++ct;
		id[i][0]=Src,id[i][cnt[i]]=Snk;
		for(int re j=1;j<=cnt[i];++j){
			NetWork::adde(id[i][j-1],id[i][j],P[i][j],0);
			NetWork::adde(id[i][j-1],id[i][j],INF,C[i][j]);
			NetWork::adde(id[i][j],id[i][j-1],INF,0);
		}
	}
	int m=gi();
	while(m--){
		int u=gi(),v=gi(),w=gi();
		for(int re j=1,k=1;j<=cnt[v];++j){
			for(;k<=cnt[u]&&S[u][k]+w<S[v][j];++k);
			NetWork::adde(id[v][j-1],id[u][k-1],INF,0);
		}
	}
	auto p=NetWork::Flow();m=gi();
	std::vector<pll> q;ll x=0,y=0;
	for(auto t:p){
		q.push_back({x,y});
		x+=t.se,y+=t.fi*t.se;
	}
	while(m--){
		ll A=gl();
		size_t i=std::lower_bound(p.begin(),p.end(),(pll){A,-INF})-p.begin();
		if(i==p.size())cout<<"-1\n";
		else cout<<(q[i].fi*A-q[i].se)<<"\n";
	}
}

inline void file(){
#ifdef Brollan
	freopen("1.in","r",stdin);
#endif
}signed main(){file();Main();return 0;}