时空限制

1S/512M

题目描述

Tom 准备到大象国拜访他的大象朋友们。

大象国有 $2^n$ 个城市，城市编号分别为 $0,1,2,\cdots,2^n-1$。Tom 的 $2^n$ 个朋友居住在不同的城市里，第 $i$ 个城市居住着他的第 $i$ 个朋友。

这 $2^n$ 个城市的连接方式为：如果两个城市 $i$ 和 $j$ 的二进制表示中恰好有一个位不同，假设这一位从低位到高位数为第 $x$ 位（$1 \le x \le n$），则这两座城市间有一条路费为 $b_x$ 的双向道路连接。

Tom 决定从兔子国乘坐飞机前往大象国，在大象国所有城市中，有 $m$ 个城市有机场，用序列 $a_1,a_2,a_3,\cdots,a_m$ 表示，开始时 Tom 可以乘坐飞机到这 $m$ 个机场的任意一个，其中降落在不同机场的机票费可能不同，降落在第 $a_i$ 号城市的机场所需要花费的费用为 $c_i$。

由于大象们都喜欢热闹，Tom 每经过一个城市（包括开始时 Tom 降落在的城市）时，这个城市的朋友就会上车跟着 Tom 一起拜访朋友们。但由于大象体重太大，会导致车需要消耗更多油才能行驶，这会导致花费很多油费，具体来说，假设目前车上有 $x$ 头大象，走一条道路需要花费 $x$ 的油费。

在 Tom 的所有朋友中，他有 $q$ 个想要拜访的朋友，他会拜访这 $q$ 个朋友的一个，为了提前处理好每种情况，他向你提出了 $q$ 个问题。在每个问题中，Tom 会告诉你他要拜访的朋友所在的城市 $f$，你需要计算出在任意一个机场降落，走城市间的道路到达朋友所在的城市 $f$ ，最少需要花费多少费用（包括机票费、开车的油费和路费）。

输入格式

第一行包含三个整数 $n,m,q$，表示有 $2^n$ 个城市，其中有 $m$ 个城市有机场和想要拜访的朋友数量 $q$。

接下来一行包含 $m$ 个整数 $a_1,a_2,a_3,\cdots,a_m$，表示有机场的城市。

接下来一行包含 $m$ 个整数 $c_1,c_2,c_3,\cdots,c_m$，表示降落在每个有机场的城市的机票费。

接下来一行包含 $n$ 个整数 $b_1,b_2,b_3,\cdots,b_n$，表示城市间的路费。

接下来 $q$ 行，每行一个整数 $f$，表示想要拜访的朋友所在的城市。

输出格式

输出 $q$ 行，每行一个整数，表示在任意一个机场降落，走城市间的道路到达 $f$ 号朋友所在的城市，最少需要花费的费用。

样例

样例输入 1

1 1 2
0
5
3
0
1

样例输出 1

5
9

样例输入 2

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

样例输出 2

5
7
4
2

样例输入 3

3 2 4
0 7
7 2
1 2 3
0
1
3
4

样例输出 3

7
9
6
8

数据范围

子任务编号	分数	$n\le$	$m,q\le$
$1$	$30$	$18$	$1000$
$2$	$30$	$14$	$16384$
$3$	$40$	$18$	$2\times 10^5$

对于 $100\%$ 的数据：$1 \le n \le 18$，$1 \le m, q \le 2 \times 10^5$，$m \le 2^n$，$0 \le a_i < 2^n$ 且 $a_i$ 互不相同，$1 \le b_i,c_i \le 10^9$，$0 \le f < 2^n$。