题目背景

啊啊 我搭上了那趟列车$\\$无论被业火灼烧多少次$\\$或是化作灰烬$\\$为何我要如此$\\$因为这是通往你的道路$\\$就算事与愿违也好$\\$还是听天由命也罢$\\$我将要改写这个世界$\\$

题目描述

Ringo 要带着企鹅罐乘坐列车前往命运所至之地寻找 Shyouma 并且完成命运换乘！

她可以通过乘坐列车在冰之世界的 $n$ 个车站中穿行，车站编号为 $1 \sim n$。

每一个车站都有两个标号，第 $i$ 个车站的标号分别为 $c_i$ 和 $d_i$。

冰之世界中一共有普通列车和特快列车两种列车。

• 任意两地之间都有一条可以往返的普通列车的线路，车站 $i$ 与车站 $j$ 之间的线路所花费的时间为 $\min(a_{c_i \mathbin{|} c_j},b_{d_i \mathbin{\&} d_j})$（$\mathbin{|}$ 表示按位或，$\mathbin{\&}$ 表示按位与）。保证 $\boldsymbol{a}$ 单调不降，$\boldsymbol{b}$ 单调不升。
• 特快列车一共有 $m$ 条线路，第 $i$ 条是从车站 $u_i$ 驶向车站 $v_i$ 的单向线路，所花费的时间为 $w_i$。

Ringo 希望能更快找到 Shyouma，不然世界就要毁灭了！

Ringo 开始的时候在车站 $1$，但是她不知道命运所至之地到底在哪里。所以她想知道对于每一个车站，如果 Shyouma 在那里，她最少需要花多少时间到达 Shyouma 所在的位置。

输入格式

第一行，三个非负整数 $n, m, k$。其中 $k$ 表示 $c_i, d_i \in [0,2^k)$。

第二行，$n$ 个非负整数 $c_1, \ldots, c_n$。

第三行，$n$ 个非负整数 $d_1, \ldots, d_n$。

第四行，$2^k$ 个非负整数 $a_0, \ldots, a_{2^k - 1}$。

第五行，$2^k$ 个非负整数 $b_0, \ldots, b_{2^k - 1}$。

保证 $\boldsymbol{a}$ 单调不降，$\boldsymbol{b}$ 单调不升。

接下来 $m$ 行，第 $i$ 行三个非负整数 $u_i, v_i, w_i$。

输出格式

仅一行，$n$ 个整数，第 $i$ 个表示从车站 $1$ 到车站 $i$ 所花费的最少的时间。

样例

5 4 3
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 7 7 8
8 7 6 5 4 3 2 1
1 2 5
2 3 4
3 4 2
4 5 3

0 4 4 6 7

样例 1 解释

Ringo 开始的时候就在车站 $1$，所以到车站 $1$ 最少的花费的时间为 $0$。

到车站 $2$ 的花费最少时间的路径为乘坐从 $1$ 到 $2$ 的普通列车，花费的时间为 $\min(a_{c_1 \mathbin{|} c_2},b_{d_1 \mathbin{\&} d_2})=\min(a_3,b_0)=\min(4,8)=4$。

到车站 $3$ 的花费最少时间的路径为乘坐从 $1$ 到 $3$ 的普通列车，花费的时间为 $4$。

到车站 $4$ 的花费最少时间的路径为乘坐从 $1$ 到 $3$ 的普通列车，花费的时间为 $4$，随后乘坐第 $3$ 条特快列车花费 $2$ 的时间从 $3$ 到 $4$，总花费时间为 $4+2=6$。

到车站 $5$ 的花费最少时间的路径为乘坐从 $1$ 到 $5$ 的普通列车，花费的时间为 $7$。

40 40 5
31 30 28 30 30 24 31 16 28 24 16 28 31 24 17 31 31 28 5 16 4 16 24 9 8 16 28 28 24 30 16 28 24 31 16 2 16 28 28 24
24 7 21 15 16 18 30 15 23 24 29 12 2 14 11 0 5 27 10 23 11 28 27 21 1 1 28 21 11 18 31 23 1 18 23 22 22 9 1 4
0 102 102 102 102 102 260 260 260 260 601 601 601 601 601 601 601 601 1264 1264 1264 1264 1264 1264 1264 1264 1264 1264 1264 1264 1264 1264
108799 106048 100679 98235 95333 90350 80153 79411 70293 69091 64328 58817 55536 53256 42932 42687 41145 40487 40047 37901 32251 29823 26460 25786 21684 20508 19995 19172 18248 12890 12397 10740
38 27 0
17 3 3
26 8 12
12 11 14
1 23 8
4 7 6
18 36 18
1 33 6
38 18 8
19 38 17
24 21 4
31 16 18
26 4 8
5 31 1
6 28 4
9 10 7
26 7 7
8 37 19
40 29 4
24 9 0
15 6 19
39 12 18
33 39 8
10 34 0
39 30 3
28 25 5
19 13 9
6 2 0
1 20 10
19 17 8
15 26 18
17 13 18
33 40 8
40 22 15
15 28 0
17 35 10
24 5 13
18 14 19
40 22 2
6 32 13

0 630 993 619 889 630 618 611 876 883 46 32 991 1026 611 629 990 1007 982 10 880 16 8 876 616 611 999 611 18 17 611 643 6 883 611 1025 611 999 14 14

数据范围

生存戦略、しましょうか

本题采用捆绑测试。

• 子任务 1（10 分）：$n\le 1000$。
• 子任务 2（10 分）：$k=0$。
• 子任务 3（20 分）：$a_i=i$，$b_i=10^{18}$。
• 子任务 4（20 分）：$m=0$，$n \ge 2$，$c_{n-1}=d_{n-1}=0$，$c_n=d_n=2^k-1$。
• 子任务 5（20 分）：$n=m=2^k$。
• 子任务 6（20 分）：无特殊限制。

对于全部的数据，$1\le n\le 10^6$，$0\le m\le10^6$，$0\le k\le 14$，$0\le c_i,d_i< 2^k$，$0\le a_i,b_i,w_i\le 10^{18}$，$1\le u_i,v_i\le n$，$a$ 单调不降，$b$ 单调不升。