P15405 [NOISG 2026 Prelim] 魔术戏法（暂无数据）

一副新格式的牌被发布。每张牌的取值是长度为 $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 \le k, m \le 1000$ ### 子任务 |子任务编号|性质内容|分值| |:-:|:-:|:-:| |1|$k \le 8$|20| |2|$k, m \le 100$|30| |3|没有特殊限制|50|