F. Subway
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In Pigeland, the subway system is quite advanced. It consists of $$$n$$$ sites, numbered from $$$1$$$ to $$$n$$$, and $$$k$$$ directed subway lines, numbered from $$$1$$$ to $$$k$$$. Subway line $$$i$$$ travels through sites $$$x_{i, 1}, x_{i, 2}, \cdots, x_{i, p_i}$$$ in order, where $$$x_{i, j}$$$ is the $$$j$$$-th site visited by line $$$i$$$. It takes $$$w_{i,j}$$$ units of time to travel from site $$$x_{i,j}$$$ to site $$$x_{i,j+1}$$$ on line $$$i$$$.

When multiple lines meet at the same site, passengers can transfer between lines. If a passenger is at a site on line $$$x$$$, while line $$$y$$$ also passes through this site, he/she can spend $$$a_y \times b_x$$$ units of time to transfer from line $$$x$$$ to line $$$y$$$, where $$$a_y$$$ and $$$b_x$$$ are given coefficients for lines $$$y$$$ and $$$x$$$. After transferring, the passenger is still at the same site, but on line $$$y$$$.

You start at site $$$1$$$. Find the minimum time needed to reach site $$$s$$$ for all $$$2 \le s \le n$$$. In particular, you can start by choosing any line at site $$$1$$$ with no transfer time cost. It is guaranteed that all sites are reachable from site $$$1$$$.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \times 10^5$$$, $$$1 \leq k \leq 2 \times 10^5$$$), indicating the number of sites and the number of subway lines.

The second line contains $$$k$$$ integers $$$a_1, a_2, \cdots, a_k$$$ ($$$1 \leq a_i \leq 10^6$$$).

The third line contains $$$k$$$ integers $$$b_1, b_2, \cdots, b_k$$$ ($$$1 \leq b_i \leq 10^6$$$).

For the following $$$k$$$ lines, the $$$i$$$-th line first contains an integer $$$p_i$$$ ($$$2 \leq p_i \leq n$$$), indicating the number of sites line $$$i$$$ travels through. Then $$$(2p_i - 1)$$$ integers $$$x_{i, 1}, w_{i, 1}, x_{i, 2}, \ldots, x_{i, p_i - 1}, w_{i, p_i - 1}, x_{i, p_i}$$$ follow ($$$1 \leq x_{i,j} \leq n$$$, $$$1 \leq w_{i,j} \leq 10^9$$$), where $$$x_{i, j}$$$ is the $$$j$$$-th site visited by line $$$i$$$, and $$$w_{i,j}$$$ is the travel time from site $$$x_{i,j}$$$ to site $$$x_{i,j+1}$$$ on line $$$i$$$. The sites traveled through by a subway line are distinct.

It is guaranteed that $$$\sum\limits_{i=1}^k (p_i - 1) \leq 2 \times 10^5$$$.

Output

Output one line containing $$$(n - 1)$$$ integers $$$d_2, d_3, \cdots, d_n$$$ separated by a space, where $$$d_i$$$ is the minimum time cost from site $$$1$$$ to site $$$i$$$.

Examples
Input
6 3
1 5 1
5 5 1
3 1 2 2 3 3
3 5 1 2 1 4
3 3 4 5 4 6
Output
2 5 21 14 18
Input
6 3
1 5 1
5 5 1
5 1 2 2 100 3 100 6 1 4
5 1 100 2 4 3 100 5 1 4
2 3 1 5
Output
2 31 43 37 136