Problem Description

A new format of cards has been released. The value of each card is a base64 string of length $k$. The character set is: {#, $, 0-9, A-Z, a-z}.

There are $n = 64^k$ cards in total, and each string appears exactly once. The sealed new deck is sorted in lexicographical order from smallest to largest.

Definition: a string $s$ is lexicographically greater than $t$ if and only if there exists a position $i$ such that $s_1 = t_1, \ldots, s_{i-1} = t_{i-1}$ and $s_i > t_i$.

The shuffle is repeated infinitely many times. Each shuffle is performed as follows:

1. Split the deck into two halves: the first half is positions $1 \sim n/2$, and the second half is positions $n/2+1 \sim n$ (the internal order of each half remains unchanged).
2. Starting from the first half, take cards alternately from the two halves. If before shuffling the positions are numbered $1 \sim n$, then after one shuffle the order becomes $\langle 1, \frac{n}{2} + 1, 2, \frac{n}{2} + 2, \ldots, \frac{n}{2}, n \rangle$.

There are $m$ tricks. The $i$-th trick requires that the card with value $x_i$ ends up at the position where the card with value $y_i$ is in the original sealed deck. Find the minimum number of shuffles needed to meet the condition. Output $0$ if it is already satisfied initially; output $-1$ if it can never be satisfied.

Input Format

• The first line contains two integers $k, m$. $(1 \le k, m \le 1000)$.
• The next $m$ lines each contain two strings $x_i, y_i$, both of length $k$. All strings use only the 64 characters above.

Output Format

For each trick, output one line with an integer: the number of shuffles needed for the condition to be satisfied for the first time; if it is impossible, output $-1$.

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

0
1
-1
3
3
-1
2

3 8
Hd7 CYZ
mZs 1Z8
iYq poa
JlP edh
SyR uxw
aCp n50
I#9 0q8
wRP t1r

2
-1
15
-1
13
-1
-1
-1

Hint

Constraints

• $1 \le k, m \le 1000$

Subtasks

Translated by ChatGPT 5