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;
using ll = long long;
using uint = unsigned int;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

struct MinCostFlow{
	using C = ll;		// capacity
	using D = ll;		// cost (distance)
	const D inf = 1e18;	// max distance

	struct edge{
		int to;
		C cap;
		D cost;
		int rev;
		edge(int to_,C cap_, D cost_, int rev_):to(to_),cap(cap_),cost(cost_),rev(rev_){}
	};
	
	int N;
	VV<edge> G;
	V<D> h;
	V<D> dist;
	V<int> prevv,preve;
	MinCostFlow(int N_):N(N_){
		G.resize(N);
		h.resize(N);
		dist.resize(N);
		prevv.resize(N);
		preve.resize(N);
	}

	void add_edge(int from, int to, C cap, D cost){
		shows("add_edge",from,to,cap,cost);
		edge e1(to,cap,cost,(int)G[to].size());
		edge e2(from,0,-cost,(int)G[from].size());
		G[from].push_back(e1);
		G[to].push_back(e2);
	}
	D min_cost_flow(int s, int t, C f){
		D res = 0;
		h = V<D>(N);
		while(f > 0){
			using P = pair<D,int>;
			priority_queue< P,vector<P>,greater<P> > que;
			dist = V<D>(N,inf);
			dist[s] = 0;
			que.push(P(0,s));
			while(!que.empty()){
				P p = que.top();
				que.pop();
				int v = p.second;
				if(dist[v] < p.first) continue;
				for(int i=0;i<(int)G[v].size();i++){
					edge &e = G[v][i];
					if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
						dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
						prevv[e.to]=v;
						preve[e.to]=i;
						que.push(P(dist[e.to],e.to));
					}
				}
			}
			if(dist[t]==inf) return -1;
			rep(v,N) h[v]+=dist[v];
			C d = f;
			for(int v=t;v!=s;v=prevv[v]){
				chmin(d,G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d*h[t];
			for(int v=t;v!=s;v=prevv[v]){
				edge &e=G[prevv[v]][preve[v]];
				e.cap-=d;
				G[v][e.rev].cap+=d;
			}
		}
		return res;
	}

	/*
		流量を横軸に、コストを縦軸に取ったときのグラフ
		各線分の (dx,dy/dx) の vector を返す
		CF621 G 
	*/
	V<pair<C,D>> min_cost_flow_slopes(int s, int t){		// {(x,tan)}
		V<pair<C,D>> res;
		h = V<D>(N);
		while(true){
			using P = pair<D,int>;
			priority_queue< P,vector<P>,greater<P> > que;
			dist = V<D>(N,inf);
			dist[s] = 0;
			que.push(P(0,s));
			while(!que.empty()){
				P p = que.top();
				que.pop();
				int v = p.second;
				if(dist[v] < p.first) continue;
				for(int i=0;i<(int)G[v].size();i++){
					edge &e = G[v][i];
					if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
						dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
						prevv[e.to]=v;
						preve[e.to]=i;
						que.push(P(dist[e.to],e.to));
					}
				}
			}
			if(dist[t]==inf) break;
			rep(v,N) h[v]+=dist[v];
			C f = inf;
			for(int v=t;v!=s;v=prevv[v]){
				chmin(f,G[prevv[v]][preve[v]].cap);
			}
			res.pb(f,h[t]);				// x, tan
			for(int v=t;v!=s;v=prevv[v]){
				edge &e=G[prevv[v]][preve[v]];
				e.cap-=f;
				G[v][e.rev].cap+=f;
			}
			if(f >= TEN(17)) break;
		}
		return res;
	}
};


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N; cin >> N;
	V<int> K(N);
	VV<ll> S(N),P(N),C(N);
	rep(i,N){
		cin >> K[i];
		S[i] = P[i] = C[i] = V<ll>(K[i]);
		rep(j,K[i]){
			cin >> S[i][j] >> P[i][j] >> C[i][j];
		}
		rep(_,K[i]-1) rep(p,K[i]-1){
			if(S[i][p] > S[i][p+1]){
				swap(S[i][p],S[i][p+1]);
				swap(P[i][p],P[i][p+1]);
				swap(C[i][p],C[i][p+1]);
			}
		}
	}

	VV<int> idx(N);
	int Vnum = 2, SS = 0, TT = 1;
	{
		rep(i,N){
			rep(j,K[i]+1){
				idx[i].pb(Vnum++);
			}
		}
	}

	MinCostFlow MCF(Vnum);

	// c * max(x-y-d,0)
	auto add = [&](int x,int y,ll d,ll c){
		MCF.add_edge(y,x,c,d);
	};
	// x-y <= d
	auto add2 = [&](int x,int y,ll d){
		const ll inf = 1e18;
		add(x,y,d,inf);
	};
	auto addE = [&](int x,int y){
		add2(x,y,0);
		add2(y,x,0);
	};

	rep(i,N){

		rep(j,K[i]){
			add(idx[i][j+1],idx[i][j],0,P[i][j]);
		}
	}
	rep(i,N){
		rep(j,K[i]){
			add2(idx[i][j],idx[i][j+1],0);
			add2(idx[i][j+1],idx[i][j],C[i][j]);
		}
		addE(SS,idx[i][0]);
		addE(TT,idx[i][K[i]]);
	}
	int M; cin >> M;
	rep(_,M){
		int j,i; ll w;
		cin >> j >> i >> w; i--,j--;
		shows(i,j,w);
		// i - j <= w
		rep(a,K[i]) rep(b,K[j]){
			if(S[i][a]-S[j][b] > w){
				add2(idx[j][b+1],idx[i][a],0);
			}
		}
	}
	auto slope = MCF.min_cost_flow_slopes(SS,TT);
	show(slope);
	using pll = pair<ll,ll>;
	{
		int K = slope.size();
		V<pll> v;
		v.pb(0,0);
		rep(i,K){
			ll x = v.back().fs;
			ll y = v.back().sc;
			x += slope[i].fs;
			y += slope[i].fs * slope[i].sc;
			v.pb(x,y);
		}
		show(v);

		int Q; cin >> Q;
		while(Q--){
			ll A; cin >> A;
			if(A > slope.back().sc){
				cout << -1 << endl;
			}else{
				rep(i,K){
					if(slope[i].sc <= A && A <= slope[i+1].sc){
						cout << -(v[i+1].sc - A * v[i+1].fs) << endl;
						break;
					}
				}
			}
		}
	}

}