Рассмотрим отрезок $$$[0, d]$$$ координатной прямой. В этом отрезке $$$n$$$ фонарей и $$$m$$$ интересных точек.
Для каждого фонаря вы должны выбрать его мощность — целое число от $$$0$$$ до $$$d$$$ (включительно). Фонарь с координатой $$$x$$$ освещает интересную точку с координатой $$$y$$$, если $$$|x - y|$$$ меньше либо равно мощности фонаря.
Способ выбрать мощности для всех фонарей является корректным, если каждая интересная точка освещена хотя бы одним фонарем.
Вам нужно обработать $$$q$$$ запросов. Каждый запрос обозначается одним целым числом $$$f_i$$$. Чтобы ответить на $$$i$$$-й запрос, вам нужно:
В первой строке заданы три целых числа $$$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
Название |
---|