No testdata at current.

你现在到了某个巨大的城市，这个城市有非常复杂的地铁网络，还有很多共享单车。

有 $r$ 条双向道路，$s$ 条地铁线路。

一共有 $n$ 个地点，标号 $1\sim n$ 。

你可以骑共享单车通过道路。

扫描和锁车总共需要 $x$ 的时间。

第 $i$ 条道路连接第 $a_i$ 和第 $b_i$ 个地点，骑共享单车通过需要 $t_i$ 的时间。

你还可以坐地铁。

每个地点都有一个地铁站（可能有的不通车），按照地点编号 $1\sim n$ 。

第 $i$ 个地铁站需要 $e_i$ 的时间进站或出站。

在第 $i$ 个地铁站换乘需要 $c_i$ 的时间。

地铁有环线和非环线两种。

每一条地铁线路都有一个起点站。

对于每条环线地铁，每天早上8:00的时候有两列列车正好分别从起点站往两个方向驶出。

对于每条非环线地铁，起点站是线路的一个端点，每天早上8:00的时候有一列列车正好从起点站驶出。列车到达线路的另一个端点之后会立刻返程，返程途中也会在经过的地铁站停车开门。

每一条线路的发车都是均匀的。

第 $i$ 条地铁线路的发车间隔是 $T_i$ 。并且没有早班车、末班车的安排，发车是持续不断的。

地铁在站与站之间行驶需要时间。

只有当你进站/换乘之后所在的地铁站有一列地铁到站停车开门时，你才能上车。

你可以等待地铁到站。

假设停车开门的时间计算在行驶时间中。

假设你出站后能立刻找到一辆能用的共享单车。

你想知道，在今天早上8:00从 $1$ 号地点出发到 $n$ 个地点中的每个地点需要多少时间 。

注意最后一次锁车或者出站的时间要算在总时间中。

输入格式 第一行四个非负整数，$n,r,s,x$ 。

第二行 $n$ 个正整数，表示 $e_i$ 。

第三行 $n$ 个正整数，表示 $c_i$ 。

接下来 $r$ 行，每行三个正整数，表示 $a_i,b_i,t_i$ 。

接下来 $s$ 行，每行若干个正整数，格式如下：

$\bullet$ 第一个正整数 $k$ ，表示铁路的段数。

$\bullet$ 接下来 $2k+1$ 个正整数 $v_1,l_1,v_2,l_2,\cdots,v_k,l_k,v_{k+1}$ ,表示铁路按顺序经过的站点和行驶时间。其中 $v_1$ 是起点站，$v_{1..k}$ 两两不相同，$v_{2..k+1}$ 两两不相同。如果 $v_{k+1}=v_1$ 则说明该线路是环线，否则该线路是非环线。地铁在到达 $v_i$ 和到达 $v_{i+1}$ 之间需要经过 $l_i$ 的时间。

$\bullet$ 最后一个正整数 $T_i$ ，表示该线路的发车间隔。保证 $T_i | 2\sum_{j=1}^k l_j$ 。如果线路是环线保证 $T_i|\sum_{j=1}^k l_j$ 。

输出格式 一行，$n$ 个非负整数，第 $i$ 个表示你从 $1$ 号地点到 $i$ 号地点的最短时间。特别地，第一个数总是 $0$ 。

样例 1 输入

4 0 1 1

6 6 6 6

2 2 2 2

3 4 3 1 7 2 15 3 10

样例 1 输出

0 26 41 16

样例 2 输入

4 5 0 13

1 1 1 1

1 1 1 1

1 3 9

1 2 10

3 4 8

4 2 6

2 3 5

样例 2 输出

0 23 22 29

样例 3 输入

13 2 3 8

14 16 16 16 16 16 16 16 16 16 16 16 16

22 32 32 32 32 32 32 32 32 20 32 32 32

3 8 4

11 13 4

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

3 7 6 8 6 9 6 10 1

2 12 12 10 12 11 1

样例 3 输出

0 33 36 39 36 33 86 48 86 92 124 124 136

样例 4 输入

13 2 3 8

14 16 16 16 16 16 16 16 16 16 16 16 16

22 32 32 32 32 32 32 32 32 20 32 32 32

3 8 4

11 13 4

6 2 3 3 3 4 3 5 3 6 3 1 3 2 18

3 7 6 8 6 9 6 10 6

2 12 12 10 12 11 8

样例 4 输出

0 34 37 40 43 40 88 49 88 94 128 128 140

保证 $1 \le n \le 100000,0 \le r \le 300000,0 \le s \le 100000,1 \le x \le 10^9$ 。

保证 $1 \le e_i,c_i,l_i \le 10^9$ 。

保证 $c_i \le 2e_i$ 。

保证 $1 \le a_i,b_i \le n,1 \le t_i \le 10^9$ 。

保证 $1 \le k \le n,\sum k \le 200000,1 \le v_i \le n$ 。

保证如果 $v_1=v_{k+1}$ 那么 $k \ge 3$ 。

保证你能够到达每个地点。

$Subtask 1(7 pts):$$s=0$ ，即没有地铁线路。

$Subtask 2(16 pts):$$s \le 5,x=0,T_i=1$

$Subtask 3(19 pts):$$s \le 5,T_i=1$

$Subtask 4(28 pts):$$T_i=1$ ，即每条地铁线路的发车间隔都是 $1$ ，这意味着幸运的你永远不需要等车。

$Subtask 5(15 pts):$$n \le 1000$

$Subtask 6(15 pts):$无特殊限制

时间限制：2s

空间限制：512MB