CF1728G.Illumination

Consider a segment $[0, d]$ of the coordinate line. There are $n$ lanterns and $m$ points of interest in this segment.

For each lantern, you can choose its power — an integer between $0$ and $d$ (inclusive). A lantern with coordinate $x$ illuminates the point of interest with coordinate $y$ if $|x - y|$ is less than or equal to the power of the lantern.

A way to choose the power values for all lanterns is considered valid if every point of interest is illuminated by at least one lantern.

You have to process $q$ queries. Each query is represented by one integer $f_i$. To answer the $i$-th query, you have to:

• add a lantern on coordinate $f_i$;
• calculate the number of valid ways to assign power values to all lanterns, and print it modulo $998244353$;
• remove the lantern you just added.

考虑坐标轴上的一段区间 $[0, d]$。该区间内有 $n$ 个灯笼和 $m$ 个兴趣点。

对每个灯笼，你可以为其选择一个功率值——一个介于 $0$ 到 $d$（含端点）之间的整数。位于坐标 $x$ 的灯笼能够照亮位于坐标 $y$ 的兴趣点，当且仅当 $|x - y|$ 不超过该灯笼的功率。

若每个兴趣点至少被一个灯笼照亮，则称这种为所有灯笼分配功率值的方式是合法的。

你需要处理 $q$ 个查询。每个查询由一个整数 $f_i$ 表示。对于第 $i$ 个查询，你需要执行以下操作：

• 在坐标 $f_i$ 处新增一个灯笼；
• 计算为当前所有灯笼分配功率值的合法方案总数，并将结果对 $998244353$ 取模后输出；
• 移除刚刚添加的灯笼。

The first line contains three integers $d$, $n$ and $m$ ($4 \le d \le 3 \cdot 10^5$; $1 \le n \le 2 \cdot 10^5$; $1 \le m \le 16$) — the size of the segment, the number of lanterns and the number of points of interest, respectively.

The second line contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \le l_i \le d - 1$), where $l_i$ is the coordinate of the $i$-th lantern.

The third line contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_i \le d - 1$), where $p_i$ is the coordinate of the $i$-th point of interest.

The fourth line contains one integer $q$ ($1 \le q \le 5 \cdot 10^5$) — the number of queries.

The fifth line contains $q$ integers $f_1, f_2, \dots, f_q$ ($1 \le f_i \le d - 1$), where $f_i$ is the integer representing the $i$-th query.

Additional constraint on the input: during the processing of each query, no coordinate contains more than one object (i. e. there cannot be two or more lanterns with the same coordinate, two or more points of interest with the same coordinate, or a lantern and a point of interest with the same coordinate).

第一行包含三个整数 $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$ 次查询所对应的整数。

输入的额外约束：在处理每次查询时，任意坐标上至多存在一个物体（即：不存在两个或更多灯笼具有相同坐标，不存在两个或更多兴趣点具有相同坐标，也不存在灯笼与兴趣点位于同一坐标）。

For each query, print one integer — the answer to it, taken modulo $998244353$.

对于每个查询，输出一个整数——该查询的答案对 $998244353$ 取模的结果。