Master Zhu 有 $n$ 个魔法数字。第 $i$ 个数字 $a_i$ 可以表示为一个长度为 $i$ 的二进制字符串，其中可以包含前导零。当我们反转并连接这些二进制字符串时，我们得到一个长度为 $\frac{n(n+1)}{2}$ 的长字符串 $s$。从 $s$ 的第 $\frac{i(i-1)}{2}$ 位到第 $\frac{i(i+1)}{2} - 1$ 位（包含边界）的子串是 $a_i$ 的二进制表示，从最低位到最高位排列。此处，长字符串 $s$ 从 0 开始索引。

有一天，Rin 将 Master Zhu 的魔法数字输入到一个程序中，以创建 $n$ 个新的魔法数字。第 $i$ 个新数字是 $b_i$。以下是该程序的 C 语言风格代码：

for (int i = 1; i <= n; i++) {
b[i] = 0,
flag[i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (((1 << (j - 1)) & a[i]) > 0) {
if (!flag[i]) {
b[i] = b[j],
flag[i] = 1;
} else {
b[i] = b[i] & b[j];
}
}
}
b[i] = b[i] ^ (1 << (i - 1));
}

在上述代码中，“x << y” 是按位左移，等价于将 $x$ 乘以 $2^y$，“x & y” 是按位与，“x ^ y” 是按位异或。我们假设数字 $a_i$ 和 $b_i$ 可以有任意多的位数。

此后，Rin 想要询问 $q$ 个问题。第 $i$ 个问题是一个数字 $c_i$，它可以表示为长度为 $len_i$ 的二进制字符串，且可以包含前导零。当我们反转并连接这些二进制字符串时，我们得到一个长度为 $L_q$ 的长字符串 $t$，其中 $L_k = \sum_{i=1}^{k} len_i$。从 $t$ 的第 $L_{i-1}$ 位到第 $L_i - 1$ 位（包含边界）的子串是 $c_i$ 的二进制表示，从最低位到最高位排列。此处，长字符串 $t$ 从 0 开始索引。

对于每个问题，Rin 要求 Illya 计算数字 $d_i$：

for (int i = 1; i <= q; i++) {
d[i] = 0;
for (int j = 1; j <= min (n, len[i]); j++) {
if (((1 << (j - 1)) & c[i]) > 0) {
d[i] = d[i] | b[j];
}
}
}

此处，“x | y” 是按位或。我们假设数字 $c_i$ 和 $d_i$ 可以有任意多的位数。

第 $i$ 个问题的答案是 $d_i$ 二进制表示中 1 的个数。请帮助 Illya 回答所有问题！

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示魔法数字的数量和长字符串 $s$ 中 1 的个数（$1 \le n \le 5000$，$1 \le m \le 10^6$）。

第二行包含 $m$ 个整数，第 $i$ 个整数 $p_i$ 表示 $s[p_i] = 1$，且 $s$ 的所有其他位均为 0（$0 \le p_i < \frac{n(n+1)}{2}$，所有 $p_i$ 互不相同）。

第三行包含两个整数 $q$ 和 $r$，分别表示问题的数量和长字符串 $t$ 中 1 的个数（$1 \le q \le 5000$，$1 \le r \le 10^6$）。

第四行包含 $q$ 个整数，第 $i$ 个整数 $len_i$ 表示第 $i$ 个查询 $c_i$ 的二进制表示长度（$1 \le len_i \le 10^9$）。保证 $L_q = \sum_{i=1}^{q} len_i$ 最多为 $10^9$。

第五行包含 $r$ 个整数，第 $i$ 个整数 $z_i$ 表示 $t[z_i] = 1$，且 $t$ 的所有其他位均为 0（$0 \le z_i < L_q$，所有 $z_i$ 互不相同）。

输出格式

对于每个问题 $i$，输出一行，包含一个整数：$d_i$ 二进制表示中 1 的个数。

样例

输入 1

3 4
0 1 4 5
3 6
2 3 3
0 1 2 4 6 7

输出 1

2
3
3