Язык племени Мотунуи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для нас на экране, конечно, показали персонажей, говорящих на родном для нас языке, однако родной язык племени Мотунуи гораздо более сложный.

Всего в языке есть n букв, а звуки, соответствующие каждой из них, мы обозначим числами a1, ..., an. Разным буквам может соответствовать один и тот же звук. Слов в языке ровно 2n - 1, и каждое из них является произвольной подпоследовательностью этих n букв (порядок букв в слове совпадает с порядком в алфавите).

Обозначим за si i-е в лексикографическом порядке звучание слова. То есть возьмем все слова языка, выпишем последовательность звуков для каждого из них, и упорядочим эти последовательности по возрастанию. Здесь мы считаем, что слово x меньше слова y, если либо последовательность звуков x — префикс последовательности звуков y, либо первый отличающийся звук в x меньше, чем соответствующий звук в y.

Ваша задача — найти k минимальных по звучанию слов языка племени острова Мотунуи. Поскольку суммарная длина этих слов может быть слишком большой, выведите вместо этого хеши этих слов, где хеш слова равен

для заранее заданных B и M.

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

В первой строке ввода даны целые числа n, k, B и M — количество букв в алфавите, количество интересующих вас слов и параметры хеша (1 ≤ k, n ≤ 105; k ≤ 2n - 1; 1 ≤ B, M ≤ 106).

Во второй строке перечислены n целых чисел ai — номера звуков каждой буквы (1 ≤ ai ≤ 105).

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

Для k лексикографически минимальных слов языка выведите по очереди хеши их звучаний по одному в каждой строке.

Примеры

Входные данные
2 3 1 5
1 2
Выходные данные
1
3
2
Входные данные
3 4 2 3
1 3 1
Выходные данные
1
1
0
2
Входные данные
5 6 23 1000
1 2 4 2 3
Выходные данные
1
25
25
577
274
578

Примечание

В первом примере порядок слов следующий: , , .

Во втором примере слова звучат как , , , , , .