NOI2025 is being held in Shaoxing. Xiao Y is creating a robot for the closing ceremony performance and plans to control it to walk from the warehouse to the auditorium.

Shaoxing’s road system can be simplified as $n$ intersections and $m$ one-way roads connecting these intersections, with each road having a certain length. To facilitate recording the road system into the robot’s chip, Xiao Y numbered all the roads connected to each intersection. Specifically, if there are $d$ roads starting from intersection $x$, Xiao Y will assign numbers to these $d$ roads in some order as $1$ to $d$, called the $1$-st to $d$-th road starting from $x$.

The robot has an internal parameter $p$. Given the upper limit $k$ of parameter $p$ and the modification costs $v_1, v_2, \dots, v_{k - 1}, \ w_2, w_3, \dots, w_k$. Xiao Y will set and modify the robot's parameter as follows:

• Initially, Xiao Y sets $p$ to $1$.
• At any time, Xiao Y can remotely control the robot to modify the parameter:
  • If $p < k$, Xiao Y can pay a cost of $v_p$ to increase $p$ by $1$, i.e., $p \gets p + 1$;
  • If $p > 1$, Xiao Y can pay a cost of $w_p$ to decrease $p$ by $1$, i.e., $p \gets p - 1$.

Initially, Xiao Y's robot is at the robot warehouse, i.e., intersection $1$. When the robot is at intersection $x$, let the $p$-th road starting from intersection $x$ have endpoint $y$ and length $z$. Then, Xiao Y can pay a cost of $z$ to control the robot to move from $x$ to $y$. In particular, if there are fewer than $p$ roads starting from $x$, then Xiao Y cannot control the robot to move.

Xiao Y does not know which intersection the auditorium for the closing ceremony is located at, so he needs to prepare for every intersection. Please help him find the minimum cost required to move the robot from the warehouse to each intersection.

Input Format

Read from standard input.

The first line contains a non-negative integer $c$, indicating the test case number. $c=0$ means this test case is the sample.

The second line contains three positive integers $n, m, k$, representing the number of intersections, the number of roads, and the upper limit of parameter $p$.

The third line contains $k-1$ non-negative integers $v_1, \dots, v_{k-1}$, representing the costs to increase parameter $p$.

The fourth line contains $k-1$ non-negative integers $w_2, \dots, w_k$, representing the costs to decrease parameter $p$.

The $i+4$-th line ($1 \le i \le n$) contains several positive integers, where the first non-negative integer $d_i$ indicates the number of roads starting from intersection $i$. Then follow $2d_i$ positive integers: $y_{i,1}, z_{i,1}, y_{i,2}, z_{i,2}, \dots, y_{i,d_i}, z_{i,d_i}$, indicating the roads starting from intersection $i$, where $y_{i,j}, z_{i,j}$ ($1 \le j \le d_i$) denote the endpoint and length of the $j$-th road respectively.

Output Format

Output to standard output.

Output a line containing $n$ integers, where the $i$-th ($1 \le i \le n$) number represents the minimum cost for Xiao Y to move the robot from the warehouse to intersection $i$. In particular, if Xiao Y cannot move the robot from the warehouse to that intersection, output $-1$.

Sample

Input

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

Output

0 5 3 4 -1

Explanation

Xiao Y can move the robot from the warehouse to intersections $1$ to $4$ as follows:

• For intersection $1$: The robot starts at intersection $1$, so the cost is $0$;
• For intersection $2$: Xiao Y controls the robot to move along the $1$-st road starting from intersection $1$ to intersection $2$, with a cost of $5$;
• For intersection $3$: Xiao Y increases parameter $p$ by $1$, then moves the robot along the $2$-nd road starting from intersection $1$ to intersection $3$, with a cost of $2 + 1 = 3$;
• For intersection $4$: Xiao Y increases parameter $p$ by $1$, then moves the robot along the $2$-nd road starting from intersection $1$ to intersection $3$, and then along the $2$-nd road starting from intersection $3$ to intersection $4$, with a cost of $2 + 1 + 1 = 4$.

It can be proven that the above movement plans all have minimum cost.

• For intersection $5$: Since Xiao Y cannot move the robot to intersection $5$, output $-1$.

Sample 2

See ex_2.in and ex_2.ans in the download directory.

This sample meets the constraints for test points $3$ to $5$.

Sample 3

See ex_3.in and ex_3.ans in the download directory.

This sample meets the constraints for test points $6$ to $8$.

Sample 4

See ex_4.in and ex_4.ans in the download directory.

This sample meets the constraints for test points $9, 10$.

Sample 5

See ex_5.in and ex_5.ans in the download directory.

This sample meets the constraints for test points $16$ to $18$.

Data Range

For all test data, it is guaranteed that:

• $1 \le n, m \le 3 \times 10^{5}$, $1 \le k \le 2.5 \times 10^{5}$;
• For all $1 \le i \le k - 1$, $0 \le v_i \le 10^9$;
• For all $2 \le i \le k$, $0 \le w_i \le 10^9$;
• For all $1 \le i \le n$, $0 \le d_i \le k$, and $\sum_{i=1}^n d_i = m$;
• For all $1 \le i \le n$, $1 \le j \le d_i$, $1 \le y_{i,j} \le n$, $1 \le z_{i,j} \le 10^9$.

Special Property A: It is guaranteed that $v_1 = v_2 = \dots = v_{k - 1} = 0$ and $w_2 = w_3 = \dots = w_k = 0$.

Special Property B: It is guaranteed that for all $1 \le i \le n$, $1 \le j \le d_i$, $z_{i,j} = 1$.

Special Property C: It is guaranteed that at most $10$ values of $i$ satisfy $d_i \ge 10$.