题目描述

在数轴上生活着 $n$ 位旅行者，编号为 $1, 2, \dots, n$，第 $i$ 位旅行者当前的位置为 $x_i$。

当第 $i$ 位旅行者想进行一次对称旅行时，他需要从旅行者 $i-1$ 和 $i+1$ 中选一个（设为 $j$），然后从现在的位置旅行到 $x_j$ 的对称点上。

旅行者们的一轮旅行包含 $m$ 次对称旅行，其中第 $i$ 次对称旅行由旅行者 $a_i$ 进行。

旅行者们期望发起 $K$ 轮旅行（每轮旅行结束后旅行者不归位），那么对于每位旅行者，所有 $2^{mK}$ 种可能的旅行方案中最终位置之和是多少？答案对 $10^9+7$ 取模。

输入格式

• 第一行一个整数 $n$
• 第二行 $n$ 个整数 $x_1, x_2, \cdots, x_n$，分别代表每枚旅行者初始时的位置
• 第三行两个整数 $m, K$
• 第四行 $m$ 个整数 $a_1, a_2, \cdots, a_m$，分别代表一轮旅行中第 $i$ 次发起对称旅行的旅行者

输出格式

一行 $n$ 个整数，代表每位旅行者的答案

3
1 0 2
1 1
2

2 6 4

样例解释 1

共 2 种跳法，旅行者 1 3 都不动，旅行者 2 可能到达 2 或 4

3
2 1 2
2 2
2 2

32 16 32

样例解释 2

共 16 种跳法，旅行者 1 3 都不动，旅行者 2 的最终位置永远是 1

5
0 1 3 6 10
3 5
2 3 4

0 65536 163840 294912 327680

附加样例

c.in
c.out

数据范围与提示

• 对于 $100 \%$ 的数据，$1 \leq n, m \leq 10^5, 1 \leq K \leq 10^{18}, 2 \leq a_i \leq n-1,0 \leq x_i \leq 10^9$
• 对于 $10 \%$ 的数据，$n \leq 10^5, m \leq 20, K=1$
• 对于 $30 \%$ 的数据，$n \leq 10^5, m \leq 2000, K \leq 2000$
• 另有 $20 \%$ 的数据，$n \leq 100, m \leq 10^5, K \leq 10^{18}$