Для нас на экране, конечно, показали персонажей, говорящих на родном для нас языке, однако родной язык племени Мотунуи гораздо более сложный.
Всего в языке есть n букв, а звуки, соответствующие каждой из них, мы обозначим числами a1, ..., an. Разным буквам может соответствовать один и тот же звук. Слов в языке ровно 2n - 1, и каждое из них является произвольной подпоследовательностью этих n букв (порядок букв в слове совпадает с порядком в алфавите).
Обозначим за si i-е в лексикографическом порядке звучание слова. То есть возьмем все слова языка, выпишем последовательность звуков для каждого из них, и упорядочим эти последовательности по возрастанию. Здесь мы считаем, что слово x меньше слова y, если либо последовательность звуков x — префикс последовательности звуков y, либо первый отличающийся звук в x меньше, чем соответствующий звук в y.
Ваша задача — найти k минимальных по звучанию слов языка племени острова Мотунуи. Поскольку суммарная длина этих слов может быть слишком большой, выведите вместо этого хеши этих слов, где хеш слова равен
В первой строке ввода даны целые числа 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
В первом примере порядок слов следующий: ,
,
.
Во втором примере слова звучат как ,
,
,
,
,
.