← 返回题目列表

Codeforces · 1728/G

G. 照明

中文机器翻译题面 查看原题

考虑坐标线的一段$$$[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