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 For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 35,inf = 1e9;
int n,m,q,tot,cnt[N],id[N][N];
ll pre[100010];
struct node{
	ll s,p,c;
}a[N][N];

namespace MCMF{
	const int N = 1010, M = 10010;
	int tot=-1,first[N],to[M<<1],last[M<<1];
	ll flow[M<<1],cost[M<<1];
	inline void init(){
		fil(first,-1);
	}
	inline void add(int x,int y,ll w,ll f){
		to[++tot]=y,flow[tot]=w,cost[tot]=f,last[tot]=first[x],first[x]=tot;
	}
	inline void Add(int x,int y,ll w,ll f){
		add(x,y,w,f),add(y,x,0,-f);
	}
	const ll inf = 1ll<<60;
	ll dis[N],Flow[N];
	int pre[N],pos[N];
	bool vis[N];
	inline bool spfa(int s,int t,int n){
		For(i,1,n) vis[i]=0,dis[i]=Flow[i]=inf;
		queue<int>q;q.push(s),dis[s]=0;
		while (!q.empty()){
			int u=q.front();q.pop(),vis[u]=0;
			for (int i=first[u];i!=-1;i=last[i]){
				int v=to[i];
				if (dis[u]+cost[i]<dis[v]&&flow[i]){
					dis[v]=dis[u]+cost[i],Flow[v]=min(Flow[u],flow[i]),pre[v]=u,pos[v]=i;
					if (!vis[v]) q.push(v),vis[v]=1;
				}
			}
		}
		return dis[t]!=inf;
	}
	inline vector<ll> solve(int S,int T,int n){
		vector<ll>ans;
		while (spfa(S,T,n)){
			if (Flow[T]>100000000) return ans.pb(dis[T]),ans;
			For(i,1,Flow[T]) ans.pb(dis[T]);
			for (int i=T;i!=S;i=pre[i]) flow[pos[i]]-=Flow[T],flow[pos[i]^1]+=Flow[T];
		}
		return ans;
	}
};

int main(){
	n=read();
	int S=1,T=2;
	tot=2,MCMF::init();
	For(i,1,n){
		cnt[i]=read(),id[i][0]=++tot;
		For(j,1,cnt[i]){
			a[i][j]=(node){read(),read(),read()};
			id[i][j]=++tot;
		}
		MCMF::Add(S,id[i][0],inf,0),MCMF::Add(id[i][cnt[i]],T,inf,0);
		sort(a[i]+1,a[i]+1+cnt[i],[](node a,node b){
			return a.s<b.s;
		});
		For(j,1,cnt[i]){
			MCMF::Add(id[i][j-1],id[i][j],a[i][j].p,0);
			MCMF::Add(id[i][j-1],id[i][j],1e9,a[i][j].c);
		}
	}
	m=read();
	while (m--){
		int u=read(),v=read(),w=read(),l=0;
		For(i,1,cnt[u]){
			while (l<cnt[v]&&a[v][l+1].s<=a[u][i].s+w) ++l;
			if (l==cnt[v]) break;
			MCMF::Add(id[v][l],id[u][i],1e9,0);
		}
	}
	auto p=MCMF::solve(S,T,tot);
	pre[0]=p[0];
	FOR(i,1,siz(p)) pre[i]=pre[i-1]+p[i];
	q=read();
	while (q--){
		ll A=read();
		int pos=lower_bound(all(p),A)-p.begin();
		if (pos==siz(p)) puts("-1");
			else printf("%lld\n",A*pos-(pos==0?0:pre[pos-1]));
	}
}