考虑坐标线的一段$$$[0, d]$$$。该路段有 $$$n$$$ 灯笼和 $$$m$$$ 兴趣点。
对于每个灯笼,您可以选择其功率 - $$$0$$$ 和 $$$d$$$(含)之间的整数。如果 $$$|x - y|$$$ 小于或等于灯笼的功率,则坐标为 $$$x$$$ 的灯笼将照亮坐标为 $$$y$$$ 的兴趣点。
如果每个兴趣点至少被一个灯笼照亮,则为所有灯笼选择功率值的方法被认为是有效的。
您必须处理 $$$q$$$ 查询。每个查询由一个整数 $$$f_i$$$ 表示。要回答第 $$$i$$$ 查询,您必须:
- 在坐标 $$$f_i$$$ 上添加灯笼;
- 计算为所有灯笼分配功率值的有效方法的数量,并将其模 $$$998244353$$$ 打印出来;
- 移除您刚刚添加的灯笼。
输入
第一行包含三个整数 $$$d$$$、$$$n$$$ 和 $$$m$$$ ($$$4 \le d \le 3 \cdot 10^5$$$; $$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 16$$$) — 段的大小,灯笼的数量和兴趣点的数量。
第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_i \le d - 1$$$),其中 $$$l_i$$$ 是第 $$$i$$$ 个灯笼的坐标。
第三行包含 $$$m$$$ 整数 $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le d - 1$$$),其中 $$$p_i$$$ 是第 $$$i$$$ 个兴趣点的坐标。
第四行包含一个整数 $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — 查询数。
第五行包含 $$$q$$$ 整数 $$$f_1, f_2, \dots, f_q$$$ ($$$1 \le f_i \le d - 1$$$),其中 $$$f_i$$$ 是代表第 $$$i$$$ 个查询的整数。
对输入的附加约束:在处理每个查询期间,没有一个坐标包含多个对象(即不能有两个或多个具有相同坐标的灯笼,两个或多个具有相同坐标的兴趣点,或者一个灯笼和一个具有相同坐标的兴趣点)。
输出
对于每个查询,打印一个整数 - 它的答案,以 $$$998244353$$$ 为模。
示例
输入 #1
6 1 1 4 3 3 2 1 5
输出 #1
48 47 47
输入 #2
6 1 2 4 2 5 2 1 3
输出 #2
44 46
输入 #3
20 1 2 11 15 7 1 8
输出 #3
413
输入#4
20 3 5 5 7 18 1 6 3 10 19 5 4 17 15 8 9
输出#4
190431 187503 188085 189903 189708