Bad Doctor

Alex got sick. He went to a clinic and visited $n$ doctors. The $i$-th doctor said that starting with day $l_i$ and ending with day $r_i$, Alex must take $k_i$ medicines: $a_1, a_2, \ldots, a_{k_i}$, one pill a day of each. Medicines are numbered from 1 to $m$.

Of course, if several doctors tell Alex to take the same medicine on the same day, he takes only one pill of that medicine that day. At least, that is how people act in real life.

One pill of medicine $j$ costs $c_j$ roubles. But Alex has a doubt: rumors say that one of the doctors in the clinic is really bad. He does not know which doctor is bad, but he decided to ignore this doctor's prescription.

Your task is to find $n$ numbers $t_i$: how much money Alex will spend on pills if the $i$-th doctor is bad.

The first line contains two integers $n$ and $m$: the number of doctors and the number of medicines ($1 \le n \le 500\,000$, $1 \le m \le 500\,000$).

The second line contains $m$ integers $c_j$: the cost of one pill of the $j$-th medicine ($1 \le c_j \le 1\,000\,000$).

Each of the next $n$ lines describes a doctor. The $i$-th of them starts with three integers $l_i, r_i, k_i$: the start and end days of the $i$-th doctor's prescription and the number of medicines he told Alex to take ($1 \le l_i \le r_i \le 1\,000\,000$, $1 \le k_i \le m$). Then follow $k_i$ distinct integers $a_1, a_2, \ldots, a_{k_i}$, each from 1 to $m$: the medicines in the prescription.

The sum of all $k_i$ in the input does not exceed $1\,000\,000$.

Output $n$ integers $t_1, t_2, \ldots, t_n$: how much money Alex will spend on pills if he ignores the $i$-th doctor's prescription.