A thermal decomposition reaction is breakdown of a compound into one or more compounds when heated.

For example$, P \rightarrow a\cdot Q + b\cdot R$ is a decomposition reaction. Here, 1 unit of P is converted into a unit of Q and b unit of R after completion of the reaction.

You are given N compounds numbered from 1 to N. The initial amount of the i^{th} compound is Q_{i}.

You are also given M equations. Every equation is of the form:
$C_{0} \rightarrow W_{1}\cdot C_{1} + W_{2}\cdot C_{2} + \ldots + W_{X}\cdot C_{X}$.

Here:
C_{0} represents the compound which will decompose into X compounds on heating.
C_{i} (1 ≤ i ≤ X ) represents the compounds into which C_{0} is decomposed.
W_{i} (1 ≤ i ≤ X ) represents the number of units of C_{i} produced due to the decomposition of C_{0}.
C_{i} > C_{i-1} for all (1 ≤ i ≤ X).

Note that a compound can decompose in at most one way only.

Find the final amount of each compound after prolonged heating. Since the number can be huge, print the answer modulo 10^{9}+7.

------ Input Format ------

• First line will contain two space separated integers N and M - the number of compounds and the number of equations.
• Second line will contain N space separated integers Q_{1}, Q_{2}, ..., Q_{N} - the initial amounts of each compound.
• The next $2\cdot M$ lines contain the details of the M equations. Each equation is represented using 2 lines.
• First line of the i^{th} equation contains two space separated integers C_{i,0}, X_{i} - the decomposing compound and the number of compounds in which it decomposes.
• Second line of the $i^{th} equation contains 2 \cdot X_{i} space separated integers W_{i,1}, C_{i,1}, W_{i,2}, C_{i,2}$,… ,W_{i,X_{i}}, C_{i,X_{i}} - the number of units and the types of compounds into which C_{i,0} decomposes.

------ Output Format ------

Print N lines. The i^{th} line contains a single integer denoting the final amount of the i^{th} compound after prolonged heating modulo 10^{9}+7.

------ Constraints ------

$0 ≤ M < N ≤ 10^{5}$
$0 ≤ Q_{i} < (10^{9}+7)$
$1 ≤ C_{i,0} < N$
$1 ≤ X_{i} ≤ (N - C_{i,0})$
$1 ≤ W_{i,j} < (10^{9}+7)$, $\forall$ $(1 ≤ j ≤ X_{i})$ and $(1 ≤ i ≤ M)$.
$C_{i, j} < C_{i,j+1}$, $\forall$ $(0 ≤ j < X_{i})$ and $(1 ≤ i ≤ M)$.
$C_{i, 0} < C_{i + 1, 0}$, $\forall$ $(1 ≤ i < M)$
- Sum of $X_{i}$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
4 2
5 10 12 2
1 2
3 2 4 3
3 1
2 4

----- Sample Output 1 ------
0
25
0
66

----- explanation 1 ------
Test Cse $1$: We have $4$ compounds initially. For better explanation, we refer the compounds $1, 2, 3,$ and $4$ as $A_{1}, A_{2}, A_{3},$ and $A_{4}$ respectively. Initially, the amount of $A_{1}, A_{2}, A_{3},$ and $A_{4}$ present is $5, 10, 12,$ and $2$ respectively.

The two equations are:
- $A_{1} \rightarrow 3 \cdot A_{2} + 4 \cdot A_{3}$
- $A_{3} \rightarrow 2 \cdot A_{4}$

We know that $1$ unit of $A_{1}$ produces $3$ units of $A_{2}$ and $4$ units of $A_{3}$. Thus, the initial $5$ units of $A_{1}$ decompose to $5\cdot 3 = 15$ units of $A_{2}$ and $5\cdot 4 = 20$ units of $A_{3}$. Note that now there are $0$ units of $A_{1}$ left.
Considering only this reaction, the updated amounts of chemicals would be $[0, 10 + 15, 12 + 20, 2] = [0, 25, 32, 2]$.

We also know that $1$ unit of $A_{3}$ decomposes to $2$ units of $A_{4}$. The total amount of $A_{3}$ available for decomposition would be $32$ units $(12$ units were available initially and $20$ units were formed due to decomposition$)$. Thus these $32$ units would produce $32\cdot 2 = 64$ units of $A_{4}$.

Thus, after prolonged heating, the amounts of compounds are $[0, 25, 0, 64+2] = [0, 25, 0, 66]$.

见题面

见题面