Рабочее место участника

Фирма Macrohard разработала новый язык программирования: P--. В этом языке имеется `K` типов целых чисел – int, longint, longlongint, …, longlong…longint (`K`-1 раз long). Числа этих типов могут принимать значения в диапазонах `0..M_0,\ 0..M_1,\ …,\ 0..M_{K-1}` соответственно.

Также, в этом языке имеется процедура вывода writef, которая имеет неограниченное количество параметров. В качестве первого параметра она получает строку, а в качестве второго и последующих может получать числа любого из поддерживаемых типов. При этом вывод осуществляется следующим способом: выводится строка, переданная первым параметром, в которой произведена подстановка параметров, а именно, вместо %i подставляется число типа int, вместо %li – число типа longint, вместо %ll…li (`j` букв l) – число типа longlong…longint (`j` раз long). Вывод числа осуществляется в системе счисления с основанием `B\ (2\ ≤\ B\ ≤\ 36)`.

Цифрами в системе счисления с основанием B являются обычные десятичные цифры и, если их недостаточно, заглавные буквы латинского алфавита в алфавитном порядке. Например, 10010=4С22, 126010=Z036.

При этом тип передаваемых параметров должен совпадать с соответствующими шаблонами. Например, если `M_0=300,\ M_1=3000,\ M_2=1000000,\ B=10`, то writef("hello %i%li", 300, 500) выведет "hello 300500".

Дана строка, которую вывела некоторая процедура writef. Выясните, какая самая короткая строка могла быть передана передана этой процедуре в качестве первого параметра. Например, для приведенного выше примера, это могла быть строка "hello %lli".

На первой строке ввода находятся числа `K` и `B\ (1\ ≤\ K\ ≤\ 50,\ 2\ ≤\ B\ ≤\ 36)`. Следующая строка содержит числа `M_0,\ M_1,\ …,\ M_{K-1}\ (0\ ≤\ M_0\ ≤\ M_1\ ≤\ …\ ≤\ M_{K-1}\ ≤\ 10^9`, числа заданы в десятичной системе счисления). На следующей строке находится текст, выведенный некоторой процедурой writef. Длина текста не превышает 200 символов. Текст не содержит символов "%".

Выведите самую короткую строку, которая могла быть передана процедуре writef в качестве первого параметра. На второй строке перечислите все остальные параметры, которые были ей переданы, числа выводите в десятичной системе счисления и разделяйте ровно одним пробелом. Если решений несколько, достаточно выдать любое.

3 10
300 3000 1000000
hello 300500

hello %lli
300500

1 4
1
hello 111

hello 111

1 2
10
hello 111

hello %i
7

1 36
1000000000
HELLO 111 3

%i %i 3
29234652 1333