题目描述

NOI2025 正在绍兴举办，小 Y 为闭幕式表演制作了一个机器人并打算操控它从仓库走到礼堂。绍兴的道路系统可以简化为 $n$ 个路口以及连接这些路口的 $m$ 条单行道路，且每条道路有一定的长度。小 Y 对每一个路口连接的所有道路进行了编号，若有 $d$ 条道路以路口 $x$ 为起点，则这 $d$ 条道路会被按照某种顺序编号为 $1 \sim d$。

小 Y 的机器人内部有一个参数 $p$，给定参数 $p$ 的上限 $k$ 与修改费用 $v_1, v_2, \dots, v_{k-1}$ 和 $w_2, w_3, \dots, w_k$，设置与修改机器人参数的规则如下：

• 初始时，参数 $p$ 设置为 $1$。
• 任意时刻可远程控制修改参数：
  • 若 $p < k$，花费 $v_p$ 的费用将 $p$ 增加 $1$，即 $p \leftarrow p + 1$。
  • 若 $p > 1$，花费 $w_p$ 的费用将 $p$ 减少 $1$，即 $p \leftarrow p - 1$。

初始时机器人位于路口 $1$，当机器人位于路口 $x$ 时，记以路口 $x$ 为起点的第 $p$ 条道路的终点为 $y$，道路长度为 $z$，则可花费 $z$ 的费用操控机器人从 $x$ 走到 $y$。若以路口 $x$ 为起点的道路不足 $p$ 条，则无法操控机器人走动。请求出将机器人从仓库移动到每个路口所需费用的最小值。

输入格式

1. 第一行包含一个非负整数 $c$，表示测试点编号，$c = 0$ 表示该测试点为样例。
2. 第二行包含三个正整数 $n, m, k$，分别表示路口数量、道路数量与参数 $p$ 的上限。
3. 第三行包含 $k - 1$ 个非负整数 $v_1, \dots, v_{k-1}$，表示增加参数 $p$ 的费用。
4. 第四行包含 $k - 1$ 个非负整数 $w_2, \dots, w_k$，表示减少参数 $p$ 的费用。
5. 第 $i + 4$（$1 \leq i \leq n$）行包含若干个正整数，其中第一个非负整数 $d_i$ 表示以路口 $i$ 为起点的道路数量，接下来 $2d_i$ 个正整数 $y_{i,1}, z_{i,1}, y_{i,2}, z_{i,2}, \dots, y_{i,d_i}, z_{i,d_i}$，表示以路口 $i$ 为起点的道路，其中 $y_{i,j}$ 和 $z_{i,j}$（$1 \leq j \leq d_i$）分别表示编号为 $j$ 的道路的终点与长度。

输出格式

输出一行 $n$ 个整数，其中第 $i$（$1 \leq i \leq n$）个数表示将机器人从仓库移动到路口 $i$ 所需费用的最小值。若无法移动到该路口，则输出 $-1$。

样例1

输入

0
4 5 2
2
1
2 2 5 3 1
1 3 2
2 1 2 4 1
0

输出

0 5 3 4 -1

样例1解释

• 路口 $1$：初始位置，费用 $0$。
• 路口 $2$：沿路口 $1$ 第 $1$ 条道路移动，费用 $5$。
• 路口 $3$：将 $p$ 增加 $1$（费用 $2$），沿路口 $1$ 第 $2$ 条道路移动（费用 $1$），总费用 $2 + 1 = 3$。
• 路口 $4$：将 $p$ 增加 $1$（费用 $2$），沿路口 $1$ 第 $2$ 条道路到路口 $3$（费用 $1$），再沿路口 $3$ 第 $2$ 条道路到路口 $4$（费用 $1$），总费用 $2 + 1 + 1 = 4$。
• 路口 $5$：无法到达，输出 $-1$。

数据范围

• $1 \leq n, m \leq 3 \times 10^5$，$1 \leq k \leq 2.5 \times 10^5$。
• 对于所有 $1 \leq i \leq k - 1$，$0 \leq v_i \leq 10^9$。
• 对于所有 $2 \leq i \leq k$，$0 \leq w_i \leq 10^9$。
• 对于所有 $1 \leq i \leq n$，$0 \leq d_i \leq k$，且 $\sum_{i=1}^n d_i = m$。
• 对于所有 $1 \leq i \leq n$，$1 \leq j \leq d_i$，$1 \leq y_{i,j} \leq n$，$1 \leq z_{i,j} \leq 10^9$。

特殊性质说明：

• A：保证 $v_1 = v_2 = \cdots = v_{k-1} = 0$ 且 $w_2 = w_3 = \cdots = w_k = 0$。
• B：保证对于所有 $1 \leq i \leq n$，$1 \leq j \leq d_i$，均有 $z_{i,j} = 1$。
• C：保证至多存在 $10$ 个 $i$ 满足 $d_i \geq 10$。