题目描述

虱子国王尼特这天有点不舒服，它周围的 $n$ 个医生立刻开出了药方：第 $i$ 个医生告诉它，从这天起的第 $L_i$ 天到第 $R_i$ 天，它应该服用 $x_{i,1},x_{i,2},\dots,x_{i,K_i}$ 这 $K_i$ 种药，每天每种药应当服用恰好一片。注意，如果有多个医生的药方里都要求尼特在第 $p$ 天服用第 $q$ 种药，那尼特在第 $p$ 天仍然只会服用一片第 $q$ 种药。编号为 $j$ 的药每片需要 $c_j$ 元钱。

然而，由于尼特的疏忽，有恰好一位庸医混进了医生队伍里，但尼特并不知道哪位医生是庸医。所以它想知道，对于所有 $1\le i\le n$，如果它按照除了第 $i$ 个医生之外的所有医生的药方吃药，它总共将花费多少钱。

输入格式

第一行两个正整数 $n,m$，分别为医生数和药片种类数。

接下来一行 $m$ 个正整数 $c_1\sim c_m$。

接下来 $n$ 行，第 $i$ 行描述第 $i$ 个医生。首先三个正整数 $L_i,R_i,K_i$，后面 $K_i$ 个正整数 $x_{i,1},x_{i,2},\dots,x_{i,K_i}$。保证 $x_{i,1},x_{i,2},\dots,x_{i,K_i}$ 互不相同。

输出格式

输出 $n$ 个非负整数，第 $i$ 个表示，如果尼特认为第 $i$ 个医生是庸医并除开他的药方，它总共将花费多少钱。

样例输入输出

样例输入 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

样例输出 1

87660 75640 87560 77650 66460

样例 1 解释

这里仅解释输出中的第一个和第五个数。

如果第一位医生是庸医，则尼特：

• 在第 $2,3$ 天会吃药片 $1,2,3$。花费 $11100\times 2=22200$ 元。
• 在第 $4,5,6,7$ 天会吃药片 $1,2,3,4$。花费 $11110\times 4=44440$ 元。
• 在第 $8$ 天会吃药片 $1,2,4$。花费 $11010$ 元。
• 在第 $9$ 天会吃药片 $1,4$。花费 $10010$ 元。

总花费 $87660$ 元。

如果第五位医生是庸医，则尼特：

• 在第 $3$ 天会吃药片 $2,3$。花费 $1100$ 元。
• 在第 $4$ 天会吃药片 $1,2,3,4$。花费 $11110$ 元。
• 在第 $5$ 天会吃药片 $1,2,4$。花费 $11010$ 元。
• 在第 $6,7$ 天会吃药片 $1,2,3,4$。花费 $11110\times 2=22220$ 元。
• 在第 $8$ 天会吃药片 $1,2,4$。花费 $11010$ 元。
• 在第 $9$ 天会吃药片 $1,4$。花费 $10010$ 元。

总花费 $66460$ 元。

样例 2/3/4

见下发文件。

样例 $2$ 满足子任务 $1$ 的限制。

样例 $3$ 满足子任务 $3$ 的限制。

样例 $4$ 满足子任务 $5$ 的限制。

数据范围

本题捆绑测试。对于所有数据：$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 \leq c_i \leq 10^6$。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$