Олимпиадный тренинг

Задача . F. Красно-белый забор

Задача

Поликарп хочет построить забор возле дома. У него есть в запасе $n$ белых досок и $k$ красных досок, которые он может использовать. Каждая доска характеризуется своей длиной — целым числом.

Хороший забор должен состоять из ровно одной красной доски и нескольких (возможно, нуля) белых досок. Красная доска должна быть самой длинной в заборе (каждая белая доска, использованная в заборе, должна быть строго короче), и последовательность длин досок забора должна быть возрастающей перед красной доской и убывающей после нее. Формально, если использовано $m$ досок, и их длины $l_1$, $l_2$, ..., $l_m$ в порядке их нахождения в заборе слева направо (назовем такой массив $[l_1, l_2, \dots, l_m]$ массивом длин), то должны выполняться следующие условия:

в заборе должна использоваться ровно одна красная доска (пусть она находится в позиции $j$);
для каждого $i \in [1, j - 1]$ $l_i < l_{i + 1}$;
для каждого $i \in [j, m - 1]$ $l_i > l_{i + 1}$.

Поликарп построит свой забор следующим образом: он поставит все доски слева направо на землю (высоту $0$), без зазоров, то есть эти доски образуют многоугольник:

$\text{[math]}$ Пример: забор с массивом длин $[3, 5, 4, 2, 1]$. Вторая доска — красная. Периметр этого забора равен $20$.

Поликарпу интересны только заборы особых периметров. У него есть $q$ любимых четных целых чисел (назовем их $Q_1$, $Q_2$, ..., $Q_q$), и для каждого такого $Q_i$, он хочет посчитать количество различных заборов с периметром $Q_i$, которые возможно построить (два забора считаются различными, если их массивы длин различны). Можете ли вы помочь ему посчитать эти значения?

Входные данные

В первой строке заданы два целых числа $n$ и $k$ ($1 \le n \le 3 \cdot 10^5$, $1 \le k \le 5$) — количество белых и красных досок в распоряжении Поликарпа.

Во второй строке заданы $n$ целых чисел $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 3 \cdot 10^5$) — длины белых досок в распоряжении Поликарпа.

В третьей строке заданы $k$ целых чисел $b_1$, $b_2$, ..., $b_k$ ($1 \le b_i \le 3 \cdot 10^5$) — длины красных досок в распоряжении Поликарпа. Все $b_i$ различны.

В четвертой строке задано единственное целое число $q$ ($1 \le q \le 3 \cdot 10^5$) — количество особых чисел.

В пятой строке заданы $q$ целых чисел $Q_1$, $Q_2$, ..., $Q_q$ ($4 \le Q_i \le 12 \cdot 10^5$, все $Q_i$ — четные) — особые числа, которые нравятся Поликарпу.

Выходные данные

Для каждого $Q_i$, выведите одно число — количество хороших заборов с периметром $Q_i$, которые может построить Поликарп, взятое по модулю $998244353$.

Примечание

Возможные заборы для первого примера, заданные своими массивами высот (красная доска выделена):

с периметром $6$: $[\textbf{2}]$;
с периметром $8$: $[1, \textbf{2}]$, $[\textbf{2}, 1]$;
с периметром $10$: $[1, \textbf{2}, 1]$, $[\textbf{4}]$;
с периметром $12$: $[1, \textbf{4}]$, $[3, \textbf{4}]$, $[\textbf{4}, 1]$, $[\textbf{4}, 3]$;
с периметром $14$: $[1, \textbf{4}, 1]$, $[1, \textbf{4}, 3]$, $[3, \textbf{4}, 1]$, $[3, \textbf{4}, 3]$, $[1, 3, \textbf{4}]$, $[\textbf{4}, 3, 1]$;
с периметром $16$: $[1, \textbf{4}, 3, 1]$, $[3, \textbf{4}, 3, 1]$, $[1, 3, \textbf{4}, 1]$, $[1, 3, \textbf{4}, 3]$;
с периметром $18$: $[1, 3, \textbf{4}, 3, 1]$.

Примеры

№	Входные данные	Выходные данные
1	5 2 3 3 1 1 1 2 4 7 6 8 10 12 14 16 18	1 2 2 4 6 4 1
2	5 5 1 2 3 4 5 1 2 3 4 5 4 4 8 10 14	1 3 5 20

time 5000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет