Problem Statement

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.