Поликарп хочет построить забор возле дома. У него есть в запасе $$$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$$$), без зазоров, то есть эти доски образуют многоугольник:
Пример: забор с массивом длин $$$[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$$$.
5 2 3 3 1 1 1 2 4 7 6 8 10 12 14 16 18
1 2 2 4 6 4 1
5 5 1 2 3 4 5 1 2 3 4 5 4 4 8 10 14
1 3 5 20
Возможные заборы для первого примера, заданные своими массивами высот (красная доска выделена):
- с периметром $$$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]$$$.
