Illumination
Contest: Educational Codeforces Round 135 (Rated for Div. 2)
Difficulty rating: 2700
Tags: binary search, bitmasks, brute force, combinatorics, dp, math, two pointers

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.

Input format:
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).

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

Constraints:
Time limit: 8.0 s
Memory limit: 512.0 MB

Example input:
6 1 1
4
3
3
2 1 5

Example output:
48
47
47

Example input:
6 1 2
4
2 5
2
1 3

Example output:
44
46

Editorial:
Let's start without the queries. How to calculate the number of ways for the given $$$n$$$ lanterns?
First, it's much easier to calculate the number of bad ways — some point of interest is not illuminated. If at least one point of interest is not illuminated, then all lanterns have power lower than the distance from them to this point of interest. More importantly, it's less than $$$d$$$. Thus, the number of good ways is $$$(d+1)^n$$$ minus the number of bad ways.
Let's use inclusion-exclusion. For a mask of non-illuminated points of interest, let's calculate the number of ways to assign the powers to the lanterns in such a way that at least these points of interest are not illuminated. All other points can be either illuminated or not. Let's call it $$$\mathit{ways}[\mathit{mask}]$$$. With the values for all masks, the answer is the sum of $$$\mathit{ways}[\mathit{mask}] \cdot (-1)^{\mathit{popcount(mask)}}$$$ over all masks.
How to calculate the value for the mask? First, let's do it in $$$O(nm)$$$ for each mask. Each lantern can have any power from $$$0$$$ to the distance to the closest point of interest inside the mask non-inclusive. Thus, we can iterate over the lanterns and find the closest point to each of them, then multiply the number of ways for all lanterns.
Let's calculate it the other way around. Initialize the answers for the masks with $$$1$$$. Then iterate over the lantern and the point of interest that will be the closest non-illuminated one to this lantern. Let the distance between them be some value $$$d$$$. Which masks will this pair affect? Let the lantern be to the right of that point of interest. The opposite can be handled similarly.
All points to the left of the chosen point can be in either state. All points between the chosen one and the lantern must be illuminated. All points to the right of the lantern and with distance smaller than $$$d$$$ must also be illumunated. All point to the right of these can be in either state. Thus, the masks look like "**..**1000..000**..**", where 1 denotes the chosen non-illuminated point.
All masks that correspond to this template will be multiplied by $$$d$$$. You have to be careful when there are two points of interest with the same distance $$$d$$$ to some lantern — one to the left of it and one to the right of it. In particular, in one case, you should force illumination on all points with distance $$$<d$$$. In another case, you should force illumination on all points with distance $$$\le d$$$.
How to multiply fast enough? We'll use a technique called sum-over-subsets. Let's express the template in terms of submasks. For a template "***100000***", all submasks of "111100000111" will be multiplied by $$$d$$$. However, we accidentally multiplied masks of form "***000000***" too. Let's cancel them by dividing the submasks of "111000000111" by $$$d$$$. Record all multiplications for all pairs, them force push them into submasks with sum-over-subsets (well, product-over-subsets in this case :)).
Now we have the values of $$$\mathit{ways}[\mathit{mask}]$$$ for all masks in basically $$$O(nm + 2^m \cdot m)$$$, give or take the time to find the points that must be forced illuminated (extra $$$O(\log m)$$$ from lower_bound or two pointers, which is not really faster).
Now for the queries. How does the answer change after an extra lantern is added? Again, let's iterate over the closest point of interest and find the mask template. All masks corresponding to this template will get multiplied by $$$d$$$. Thus, the answer will change by the sum of values of these masks, multiplied by $$$d$$$, including the inclusion-exclusion coefficient. How to handle that? Well, yet another sum-over-subsets. Just collect the sum of values over the submasks beforehand and use these during the query. That gives us an $$$O(m)$$$ per query.
Overall complexity: $$$O(nm + qm + 2^m \cdot m)$$$.