坡旅甲想要在他的房子附近建一道栅栏。他有 $$$n$$$ 白板和 $$$k$$$ 红板,可以用来构建它。每块板的特征是它的长度,它是一个整数。
一个好的栅栏应该由一块红板和几块(可能是零块)白板组成。红板应该是栅栏中最长的一块(栅栏中使用的每块白板都应该严格较短),板的长度顺序应该是在红板之前升序,在红板之后降序。形式上,如果使用 $$$m$$$ 板,并且它们的长度为 $$$l_1$$$、$$$l_2$$$、...、$$$l_m$$$ 按照它们在栅栏中的放置顺序从左到右(我们将此数组称为 $$$[l_1, l_2, \dots, l_m]$$$ 长度数组),则应满足以下条件:
- 围栏中应该有一块红板(让它的索引为$$$j$$$);
- 对于 [1, j - 1]$$$ $$$l_i < l_{i + 1}$$$ 中的每个 $$$i \;
- 对于 [j, m - 1]$$$ $$$l_i > l_{i + 1}$$$ 中的每个 $$$i \。
当Polycarp建造他的栅栏时,他会将所有木板从左到右放置在$$$0$$$的同一高度上,没有任何间隙,因此这些木板组成一个多边形:
示例:以 $$$[3, 5, 4, 2, 1]$$$ 作为长度数组的栅栏。第二块板是红色的。栅栏的周长是$$$20$$$。
Polycarp 对一些特殊周长的栅栏感兴趣。他有 $$$q$$$ 甚至他真正喜欢的整数(这些整数是 $$$Q_1$$$、$$$Q_2$$$、...、$$$Q_q$$$),并且对于每个这样的整数 $$$Q_i$$$,他想要计算他可以构建的周长为 $$$Q_i$$$ 的不同栅栏的数量(如果两个栅栏的长度数组不同,则认为它们是不同的)。你能帮他计算这些值吗?
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le k \le 5$$$) — Polycarp 拥有的白板和红板的数量。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$) — Polycarp 拥有的白板的长度。
第三行包含 $$$k$$$ 整数 $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$ ($$$1 \le b_i \le 3 \cdot 10^5$$$) — Polycarp 拥有的红板的长度。所有 $$$b_i$$$ 都是不同的。
第四行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 特殊整数的数量。
第五行包含 $$$q$$$ 整数 $$$Q_1$$$, $$$Q_2$$$, ..., $$$Q_q$$$ ($$$4 \le Q_i \le 12 \cdot 10^5$$$, 每个 $$$Q_i$$$ 都是偶数) — Polycarp 喜欢的特殊整数。
输出
对于每个 $$$Q_i$$$,打印一个整数 — Polycarp 可以建造的周长为 $$$Q_i$$$ 的良好围栏数量,以 $$$998244353$$$ 为模。
示例
输入 #1
5 2 3 3 1 1 1 2 4 7 6 8 10 12 14 16 18
输出 #1
1 2 2 4 6 4 1
输入 #2
5 5 1 2 3 4 5 1 2 3 4 5 4 4 8 10 14
输出 #2
1 3 5 20
注意
第一个示例中可能的栅栏由其长度数组表示(红板的长度突出显示):
- 周长 $$$6$$$: $$$[\textbf{2}]$$$;
- 周长 $$$8$$$: $$$[1, \textbf{2}]$$$, $$$[\textbf{2}, 1]$$$;
- 周长 $$$10$$$: $$$[1, \textbf{2}, 1]$$$, $$$[\textbf{4}]$$$;
- 周长 $$$12$$$: $$$[1, \textbf{4}]$$$, $$$[3, \textbf{4}]$$$, $$$[\textbf{4}, 1]$$$, $$$[\textbf{4}, 3]$$$;
- 周长 $$$14$$$: $$$[1, \textbf{4}, 1]$$$, $$$[1, \textbf{4}, 3]$$$, $$$[3, \textbf{4}, 1]$$$, $$$[3, \textbf{4}, 3]$$$, $$$[1, 3, \textbf{4}]$$$, $$$[\textbf{4}, 3, 1]$$$;
- 周长 $$$16$$$: $$$[1, \textbf{4}, 3, 1]$$$, $$$[3, \textbf{4}, 3, 1]$$$, $$$[1, 3, \textbf{4}, 1]$$$, $$$[1, 3, \textbf{4}, 3]$$$;
- 周长 $$$18$$$:$$$[1, 3, \textbf{4}, 3, 1]$$$。