G. Освещение
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим отрезок $$$[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$$$.

Примеры
Входные данные
6 1 1
4
3
3
2 1 5
Выходные данные
48
47
47
Входные данные
6 1 2
4
2 5
2
1 3
Выходные данные
44
46
Входные данные
20 1 2
11
15 7
1
8
Выходные данные
413
Входные данные
20 3 5
5 7 18
1 6 3 10 19
5
4 17 15 8 9
Выходные данные
190431
187503
188085
189903
189708