Alex 生病了。他去了一家诊所，看了 $n$ 位医生。第 $i$ 位医生说，从第 $l_i$ 天开始到第 $r_i$ 天结束，Alex 必须服用 $k_i$ 种药物：$a_1, a_2, \dots, a_{k_i}$，每天每种药各服用一颗。药物编号从 $1$ 到 $m$。

当然，如果几位医生在同一天要求 Alex 服用同一种药，他当天只会服用一颗该药物。至少在现实生活中人们是这样做的。

第 $j$ 种药物每颗的价格为 $c_j$ 卢布。但 Alex 有个疑虑：传言说诊所里有一位医生是庸医。他不知道哪位医生是庸医，但他决定忽略这位医生的处方。

你的任务是找出 $n$ 个数字 $t_i$：即如果忽略第 $i$ 位医生的处方，Alex 将花费多少钱买药。

输入格式

第一行包含两个整数 $n$ 和 $m$：医生数量和药物数量 ($1 \le n \le 500\,000$, $1 \le m \le 500\,000$)。

第二行包含 $m$ 个整数 $c_j$：第 $j$ 种药物每颗的价格 ($1 \le c_j \le 1\,000\,000$)。

接下来的 $n$ 行，每行描述一位医生。第 $i$ 行首先包含三个整数 $l_i, r_i, k_i$：第 $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, \dots, a_{k_i}$，每个数都在 $1$ 到 $m$ 之间，表示处方中的药物。

输入中所有 $k_i$ 的总和不超过 $1\,000\,000$。

输出格式

输出 $n$ 个整数 $t_1, t_2, \dots, t_n$：即如果忽略第 $i$ 位医生的处方，Alex 将花费多少钱买药。

样例

样例输入 1

5 4
1000 100 10 1
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

样例输出 1

8766 7564 8756 7765 6646