Индивидуальная олимпиада по информатике и программированию (ИОИП)

Задача №114774. Колода для фокусов

Недавно были выпущены колоды игральных карт нового формата. Значение каждой карты в колоде задается base64 -строкой длины $k$. В рамках данной задачи под base64 -строкой подразумевается строка, каждый символ которой может принимать одно из следующих $64$ значений: ' # ', ' $ ', ' 0 '–' 9 ', ' A '–' Z ' и ' a '–' z '.

Каждая колода состоит из $n = 64^k$ карт и содержит ровно по одной карте с каждым возможным значением. Более того, в запечатанной новой колоде карты расположены в порядке лексикографического возрастания их значений. Напомним, что строка $s$ лексикографически больше строки $t$ тогда и только тогда, когда для некоторого $i$ верно, что $s_1 = t_1$, ..., $s_{i - 1} = t_{i - 1}$, а $s_i > t_i$. Иными словами, когда после их общего (возможно, пустого) префикса в $s$ идет больший символ, чем в $t$.

Фокусник Чоно Урёку перемешивает колоду, бесконечное количество раз повторяя следующее действие:

сначала он разделяет колоду на две половины — в первой оказываются карты, находившиеся на позициях от $1$ до $\frac{n}{2}$, во второй — от $\frac{n}{2} + 1$ до $n$ (порядок карт не меняется);
затем он собирает колоду заново, строго чередуя карты из двух половин, начиная с первой: если до перемешивания пронумеровать карты от $1$ до $n$, то после перемешивания колода будет выглядеть следующим образом: \left\langle 1, \tfrac{n}{2} + 1, 2, \tfrac{n}{2} + 2, \ldots, \tfrac{n}{2}, n \right\rangle \text{.}

Чоно собирается показать $m$ фокусов. Чтобы $i$-й фокус удался, ему необходимо, чтобы карта со значением $x_i$ оказалась на позиции, на которой в изначальной (запечатанной) колоде находилась карта со значением $y_i$. Считая, что для каждого фокуса Чоно берет новую запечатанную колоду, помогите ему определить, какое минимальное число перемешиваний понадобится для каждого фокуса.

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

В первой строке ввода через пробел даны два целых числа $k$ и $m$ — длина значения каждой карты и количество фокусов ($1 \leqslant k \leqslant 2500$; $1 \leqslant m \leqslant 1000$).

В следующих $m$ строках перечислены описания фокусов. В $i$-й их них через пробел даны две строки $x_i$ и $y_i$ — значения карт, фигурирующих в $i$-м фокусе ($|x_i| = |y_i| = k$). Гарантируется, что $x_i$ и $y_i$ состоят только из указанных в условии символов.

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

Для каждого фокуса выведите в отдельной строке номер перемешивания, после которого карта со значением $x_i$ впервые окажется на позиции $y_i$.

Если карта изначально находится на нужной позиции, выведите $0$. Если же такое событие никогда не произойдет, выведите $-1$.

Система оценки

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

Подзадача	Баллы	Дополнительные ограничения	Необходимые подзадачи	Информация о проверке
1	8	$k = 1$, $m \leqslant 200$	–	полная
2	11	$k \leqslant 10$, все $x_i$ равны между собой	–	полная
3	13	$k \leqslant 2$	1	полная
4	12	$k \leqslant 50$, $m \leqslant 200$	–	полная
5	18	$k, m \leqslant 300$	4	полная
6	19	$k = 1024$, $m \leqslant 700$	–	первая ошибка
7	19	нет	1 – 6	первая ошибка

Примечание

ASCII коды используемых в значениях карт символов принимают значения $35$ (' # '), $36$ (' $ '), от $48$ до $57$ (цифры), от $65$ до $90$ (заглавные латинские буквы) и от $97$ до $122$ (строчные латинские буквы).

Примеры

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

1 7
# #
U $
4 3
t D
D t
2 $
$ 2

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

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

3 8
Hd7 CYZ
mZ$ 1Z8
iYq poa
JlP edh
SyR uxw
aCp n5O
I#g Oq8
wrP tir

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

Сдать: для сдачи задач необходимо войти в систему