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;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<int>
#define mem(a) memset((a),0,sizeof(a))
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x.size()))
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ll rnd(){
	ull ans=0;
	For(i,0,4)ans=ans<<15^rand();
	return ans%((ull)1<<63);
}
const ll inf=1e18;
const int N=1005,M=500005,NN=35;
int k[NN],s[NN][NN],p[NN][NN],id[NN][NN];
int nedge=1,son[N],nextt[M],ed[M];
int di[M],QQ;
bool vis[N];
int last[N],que[N],laedge[N];
ll cost[M],dist[N],sum[M],qq[M],c[NN][NN];
bool spfa(int s,int t,int n){
    for (int i=1;i<=n;i++) {dist[i]=inf;last[i]=laedge[i]=vis[i]=que[i-1]=0;}
    int tot=1,l=0,r=0; que[0]=s; vis[s]=true; dist[s]=0;
    while (tot) {
        int k=que[l];
        vis[k]=false;
        if (++l==n) l=0;
        tot--; 
        for(int i=son[k];i;i=nextt[i]){
            if(di[i]>0&&dist[ed[i]]>dist[k]+cost[i]){
                dist[ed[i]]=dist[k]+cost[i]; laedge[ed[i]]=i; last[ed[i]]=k;
                if(vis[ed[i]]==0) {
                    if(++r==n)r=0;
                    que[r]=ed[i]; tot++; vis[ed[i]]=true;
                }
            }
        }
    }
    return last[t]>0;
}
void costflow(int s,int t,int n){
    while(spfa(s,t,n)){
        int mmin=1e9; 
        for(int i=t;last[i];i=last[i])
		{mmin=min(mmin,di[laedge[i]]);}
        //cout<<dist[t]<<" "<<mmin<<" "<<QQ<<" "<<last[12]<<" fjzqq\n";
		if(mmin>100000000){
			qq[++QQ]=dist[t]; break;
		}
		For(i,1,mmin)qq[++QQ]=dist[t];
        for(int i=t;last[i];i=last[i]){
            di[laedge[i]]-=mmin;
            di[laedge[i]^1]+=mmin;
        }
    }
}
inline void aedge(int a,int b,int c,ll d){
    nextt[++nedge]=son[a]; son[a]=nedge; ed[nedge]=b; di[nedge]=c; cost[nedge]=d;
}
inline void ins(int a,int b,int c,ll d){
	//cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
    aedge(a,b,c,d); aedge(b,a,0,-d);
}
int main(){
	#ifdef Brollan
		freopen("1.in","r",stdin);
	#endif
	int n=read();
	int sss=1,ttt=2; int nodecnt=2;
	For(i,1,n){
		k[i]=read();
		id[i][0]=++nodecnt;
		For(j,1,k[i]){
			cin>>s[i][j]>>p[i][j]>>c[i][j];
			id[i][j]=++nodecnt;
		}
		ins(sss,id[i][0],1e9,0); ins(id[i][k[i]],ttt,1e9,0);
		For(j,1,k[i]){
			For(o,j+1,k[i])if(s[i][j]>s[i][o]){
				swap(s[i][j],s[i][o]); swap(p[i][j],p[i][o]); swap(c[i][j],c[i][o]);
			}
		}
	}
	For(i,1,n){
		For(j,1,k[i]){
			ins(id[i][j-1],id[i][j],p[i][j],0);
			ins(id[i][j-1],id[i][j],1e9,c[i][j]);
		}
	}
	int m=read();
	while(m--){
		int u=read(),v=read(),w=read(),j=0;
		For(i,0,k[u]){
			while(j<k[v]&&s[v][j+1]<=s[u][i]+w)j++;
			//cout<<v<<" "<<j<<" "<<u<<" dsa "<<i<<" "<<k[v]<<" "<<s[v][j+1]<<endl;
			//if(j==k[v])break;
			ins(id[v][j],id[u][i],1e9,0);
		}
	}
	costflow(sss,ttt,nodecnt);
	For(i,1,QQ)sum[i]=sum[i-1]+qq[i];
	int q=read();
	while(q--){
		ll AA=read();
		int p=lower_bound(qq+1,qq+QQ+1,AA)-qq;
		if(p>QQ)puts("-1");
		else writeln(AA*(p-1)-sum[p-1]);
	}
}