照明

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

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

你可以给每个灯笼选择一个 $0$ 到 $d$（均包含）的整数功率。坐标为 $x$、功率为 $w$ 的灯笼能照亮坐标为 $y$ 的兴趣点，当且仅当 $|x-y|\le w$。若每个兴趣点都被至少一个灯笼照亮，则称这组功率分配合法。

有 $q$ 次相互独立的询问。每次询问先在坐标 $f_i$ 临时加入一个灯笼，求此时合法功率分配的数量，然后移除临时灯笼。答案对 $998244353$ 取模。

输入格式

第一行包含整数 $d,n,m$。

第二行包含 $n$ 个整数 $l_1,\ldots,l_n$，表示原有灯笼坐标。

第三行包含 $m$ 个整数 $p_1,\ldots,p_m$，表示兴趣点坐标。

第四行包含整数 $q$。第五行包含 $q$ 个整数 $f_1,\ldots,f_q$。

处理任意一次询问时，任一坐标至多有一个对象。换言之，原有灯笼坐标两两不同，兴趣点坐标两两不同，两类坐标互不重合，且每个 $f_i$ 都不与原有对象重合。不同询问的 $f_i$ 可以相同。

输出格式

对每次询问输出一行一个整数。

样例输入 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

数据范围

对于全部数据，$4\le d\le3\times10^5$，$1\le n\le2\times10^5$，$1\le m\le16$，$1\le q\le5\times10^5$，且 $1\le l_i,p_i,f_i\le d-1$。