Колода для фокусов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно были выпущены колоды игральных карт нового формата. Значение каждой карты в колоде задается 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. сначала он разделяет колоду на две половины — в первой оказываются карты, находившиеся на позициях от $$$1$$$ до $$$\frac{n}{2}$$$, во второй — от $$$\frac{n}{2} + 1$$$ до $$$n$$$ (порядок карт не меняется);
  2. затем он собирает колоду заново, строго чередуя карты из двух половин, начиная с первой: если до перемешивания пронумеровать карты от $$$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$$$.

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

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
18$$$k = 1$$$, $$$m \leqslant 200$$$полная
211$$$k \leqslant 10$$$, все $$$x_i$$$ равны между собойполная
313$$$k \leqslant 2$$$1полная
412$$$k \leqslant 50$$$, $$$m \leqslant 200$$$полная
518$$$k, m \leqslant 300$$$4полная
619$$$k = 1024$$$, $$$m \leqslant 700$$$первая ошибка
719нет1 – 6первая ошибка

Примеры

Входные данные
1 7
# #
U $
4 3
t D
D t
2 $
$ 2
Выходные данные
0
1
-1
3
3
4
2
Входные данные
3 8
Hd7 CYZ
mZ$ 1Z8
iYq poa
JlP edh
SyR uxw
aCp n5O
I#g Oq8
wrP tir
Выходные данные
2
13
15
-1
13
17
-1
1

Примечание

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