King Nit the louse is feeling a bit unwell, and the $n$ doctors around him have immediately prescribed treatments: the $i$-th doctor tells him that from day $L_i$ to day $R_i$, he should take $K_i$ types of medicine, specifically $x_{i,1}, x_{i,2}, \dots, x_{i,K_i}$, taking exactly one pill of each type per day. Note that if multiple doctors' prescriptions require Nit to take the $q$-th type of medicine on day $p$, Nit will still only take one pill of that type on day $p$. Each pill of type $j$ costs $c_j$.

However, due to Nit's negligence, exactly one quack doctor has mixed into the group, but Nit does not know which one it is. Therefore, he wants to know, for each $1 \le i \le n$, what the total cost would be if he followed the prescriptions of all doctors except for the $i$-th one.

Input

The first line contains two positive integers $n$ and $m$, representing the number of doctors and the number of medicine types, respectively.

The next line contains $m$ positive integers $c_1 \sim c_m$.

The next $n$ lines each describe a doctor. The $i$-th line starts with three positive integers $L_i, R_i, K_i$, followed by $K_i$ positive integers $x_{i,1}, x_{i,2}, \dots, x_{i,K_i}$. It is guaranteed that $x_{i,1}, x_{i,2}, \dots, x_{i,K_i}$ are distinct.

Output

Output $n$ non-negative integers, where the $i$-th integer represents the total cost if Nit considers the $i$-th doctor to be the quack and excludes his prescription.

Examples

Input 1

5 4
10000 1000 100 10
3 4 2 2 3
4 8 3 1 2 4
6 7 2 3 4
8 9 2 1 4
2 6 3 1 2 3

Output 1

87660 75640 87560 77650 66460

Note 1

Only the first and fifth values in the output are explained here.

If the first doctor is the quack, then Nit:

• Takes pills $1, 2, 3$ on days $2, 3$. Cost: $11100 \times 2 = 22200$.
• Takes pills $1, 2, 3, 4$ on days $4, 5, 6, 7$. Cost: $11110 \times 4 = 44440$.
• Takes pills $1, 2, 4$ on day $8$. Cost: $11010$.
• Takes pills $1, 4$ on day $9$. Cost: $10010$.

Total cost: $87660$.

If the fifth doctor is the quack, then Nit:

• Takes pills $2, 3$ on day $3$. Cost: $1100$.
• Takes pills $1, 2, 3, 4$ on day $4$. Cost: $11110$.
• Takes pills $1, 2, 4$ on day $5$. Cost: $11010$.
• Takes pills $1, 2, 3, 4$ on days $6, 7$. Cost: $11110 \times 2 = 22220$.
• Takes pills $1, 2, 4$ on day $8$. Cost: $11010$.
• Takes pills $1, 4$ on day $9$. Cost: $10010$.

Total cost: $66460$.

Examples 2/3/4

See the provided files.

Example $2$ satisfies the constraints of Subtask $1$.

Example $3$ satisfies the constraints of Subtask $3$.

Example $4$ satisfies the constraints of Subtask $5$.

Constraints

This problem uses bundled testing. For all data: $1 \le n, m \le 5 \times 10^5$, $1 \le L_i \le R_i \le 10^6$, $1 \le K_i \le m$, $\sum K_i \le 10^6$, $1 \le c_i \le 10^6$.