题目描述

一副新格式的牌被发布。每张牌的取值是长度为 $k$ 的 base64 字符串。字符集为：{#, $, 0-9, A-Z, a-z}。

共 $n = 64^k$ 张牌，每个字符串恰好出现一次。密封新牌按字典序从小到大排列。

定义：字符串 $s$ 在字典序上大于 $t$ 当且仅当存在某个位置 $i$，使得 $s_1 = t_1, \ldots, s_{i-1} = t_{i-1}$ 且 $s_i > t_i$。

洗牌重复进行无限次，每次如下：

1. 将牌堆分成前后两半：前半为位置 $1 \sim n/2$，后半为位置 $n/2+1 \sim n$（各自内部顺序不变）。
2. 从前半开始，两半交替取牌。若洗牌前编号为 $1 \sim n$，一次洗牌后的顺序为 $\langle 1, \frac{n}{2} + 1, 2, \frac{n}{2} + 2, \ldots, \frac{n}{2}, n \rangle$。

有 $m$ 个戏法。第 $i$ 个戏法要求：值为 $x_i$ 的牌出现在原始密封牌中值为 $y_i$ 的牌所在的位置。求达到条件的最少洗牌次数。若初始已满足则为 0；若永远不能则为 -1。

输入格式

• 第一行两个整数 $k, m$。$(1 \le k, m \le 1000)$
• 接下来 $m$ 行，每行两个长度均为 $k$ 的字符串 $x_i, y_i$。所有字符串仅使用上述 64 个字符。

输出格式

对每个戏法输出一行，一个整数，为首次满足条件所需的洗牌次数；若不可能则输出 -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

提示

数据规模与约定

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

子任务