[Solution] Illumination Codeforces Solution | Solution Codeforces

G. Illumination

time limit per test

8 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Consider a segment [0,𝑑]$[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$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$998244353$;
• remove the lantern you just added.

Input

The first line contains three integers 𝑑$d$, 𝑛$n$ and 𝑚$m$ (4≤𝑑≤3⋅105$4\le d\le 3\cdot {10}^5$; 1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$; 1≤𝑚≤18$1\le m\le 18$) — the size of the segment, the number of lanterns and the number of points of interest, respectively.

The second line contains 𝑛$n$ integers 𝑙1,𝑙2,…,𝑙𝑛$l_1,l_2,\dots ,l_n$ (1≤𝑙𝑖≤𝑑−1$1\le l_i\le d-1$), where 𝑙𝑖$l_i$ is the coordinate of the 𝑖$i$-th lantern.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The third line contains 𝑚$m$ integers 𝑝1,𝑝2,…,𝑝𝑚$p_1,p_2,\dots ,p_m$ (1≤𝑝𝑖≤𝑑−1$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≤𝑞≤5⋅105$1\le q\le 5\cdot {10}^5$) — the number of queries.

The fifth line contains 𝑞$q$ integers 𝑓1,𝑓2,…,𝑓𝑞$f_1,f_2,\dots ,f_q$ (1≤𝑓𝑖≤𝑑−1$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

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