Обереги тумар
В мастерской в Бишкеке делают тумары — серебряные обереги. На каждом из n оберегов выбит код a[i] — целое число от 0 до 2^B − 1. Мастер собирает цепочку из K оберегов: на каждое из K мест по очереди кладёт любой из n оберегов (копий сколько угодно, так что один оберег может встречаться в цепочке несколько раз). Цепочки различаются, если на каком-то месте лежат обереги с разными номерами.
«Сила» цепочки — побитовое исключающее ИЛИ (XOR) кодов всех её оберегов. Для каждого из q заказов x найдите, сколько существует цепочек с силой x, по модулю 998244353.
Входные данные
В первой строке — четыре целых числа B, n, K, q (1 ≤ B ≤ 17, 1 ≤ n ≤ 2 · 10⁵, 1 ≤ K ≤ 10¹⁸, 1 ≤ q ≤ 10⁵). Во второй строке — n чисел a[i] (0 ≤ a[i] < 2^B). В третьей строке — q чисел x (0 ≤ x < 2^B).
Выходные данные
Для каждого заказа выведите в отдельной строке количество цепочек по модулю 998244353.
Пример 1
Вход:
2 3 2 4
1 2 3
0 1 2 3
Выход:
3
2
2
2
Пояснение
Обереги с кодами 1, 2, 3, цепочки из двух оберегов: всего 9 цепочек. Сила 0 у цепочек (1, 1), (2, 2), (3, 3); сила 1 — у (2, 3) и (3, 2); сила 3 — у (1, 2) и (2, 1).
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов B ≤ 4 и K ≤ 30.
Подсказка
Преобразование Адамара (Уолша) превращает XOR-свёртку в поэлементное умножение.
Комментарии