나쁜 의사

Alex는 병이 났다. 그는 병원에 가서 $n$명의 의사를 만났다. $i$번째 의사는 $l_i$일부터 $r_i$일까지 Alex가 $k_i$개의 약, 즉 $a_1, a_2, \ldots, a_{k_i}$를 하루에 하나씩 복용해야 한다고 말했다. 약은 1번부터 $m$번까지 번호가 붙어 있다.

물론 여러 의사가 같은 날 같은 약을 복용하라고 하면, Alex는 그날 그 약을 한 알만 복용한다. 적어도 사람들은 실제 생활에서 그렇게 한다.

$j$번째 약 한 알의 가격은 $c_j$루블이다. 그런데 Alex는 의심이 든다. 소문에 따르면 이 병원의 의사 중 한 명은 정말 나쁜 의사라고 한다. 어느 의사가 나쁜지는 모르지만, 그는 그 의사의 처방을 무시하기로 했다.

$i$번째 의사가 나쁘다고 할 때 Alex가 약값으로 얼마를 쓰게 되는지, 즉 $n$개의 수 $t_i$를 구하시오.

첫 번째 줄에 두 정수 $n$과 $m$이 주어진다. $n$은 의사의 수, $m$은 약의 수이다. ($1 \le n \le 500\,000$, $1 \le m \le 500\,000$)

두 번째 줄에 $m$개의 정수 $c_j$가 주어진다. $c_j$는 $j$번째 약 한 알의 가격이다. ($1 \le c_j \le 1\,000\,000$)

다음 $n$개의 줄에 각 의사에 대한 정보가 주어진다. $i$번째 줄은 세 정수 $l_i, r_i, k_i$로 시작한다. $l_i$와 $r_i$는 $i$번째 의사가 처방한 복용 기간의 시작일과 종료일이고, $k_i$는 그가 Alex에게 복용하라고 한 약의 수이다. ($1 \le l_i \le r_i \le 1\,000\,000$, $1 \le k_i \le m$) 이어서 $k_i$개의 서로 다른 정수 $a_1, a_2, \ldots, a_{k_i}$가 주어진다. 각 수는 1부터 $m$까지이며, 처방에 포함된 약의 번호이다.

입력에 주어지는 모든 $k_i$의 합은 $1\,000\,000$을 넘지 않는다.

$i$번째 의사의 처방을 무시할 때 Alex가 약값으로 쓰게 되는 금액 $t_1, t_2, \ldots, t_n$을 $n$개의 정수로 출력한다.