AT_arc193_d.[ARC193D] Magnets

给定两个仅由 0 和 1 组成的长度为 $N$ 的字符串 $A = A_1A_2\ldots A_N$ 和 $B = B_1B_2\ldots B_N$。

有 $N$ 个单元格从左到右排成一列。对于 $i = 1, 2, \ldots, N$，左数第 $i$ 个单元格称为单元格 $i$。初始时，若 $A_i = $ 1，则单元格 $i$ 放置 $1$ 个棋子；若 $A_i = $ 0，则单元格 $i$ 没有棋子。

你可以进行任意次数（包括 $0$ 次）的以下操作：

1. 首先选择整数 $i$（$1 \leq i \leq N$）。
2. 然后，将所有棋子同时向单元格 $i$ 靠近的方向移动 $1$ 个单元格。具体规则如下：设某个棋子移动前的位置为单元格 $j$，移动后的位置为单元格 $j'$，
   • 若 $i < j$，则 $j' = j - 1$；
   • 若 $i > j$，则 $j' = j + 1$；
   • 若 $i = j$，则 $j' = j$。

请判断是否可以通过上述操作使网格满足以下条件，若可能，还需输出达成该条件所需的最小操作次数：

对于所有 $i = 1, 2, \ldots, N$，当且仅当 $B_i = $ 1 时，单元格 $i$ 中存在至少 $1$ 个棋子。

给定 $T$ 个独立的测试用例，请分别输出每个用例的答案。

输入通过标准输入给出，格式如下：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。每个测试用例的格式为：

$N$ $A$ $B$

输出 $T$ 行。对于第 $i$ 个测试用例：

• 若无法满足条件，输出 -1；
• 若可以满足条件，输出所需的最小操作次数。

约束条件

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 10^6$
• $T, N$ 为整数
• $A, B$ 均为仅由 0 和 1 组成的长度为 $N$ 的字符串
• 存在至少一个 $i$ 满足 $A_i = $ 1
• 存在至少一个 $i$ 满足 $B_i = $ 1
• 所有测试用例的 $N$ 之和不超过 $10^6$

样例解释 1

输入包含 $3$ 个独立测试用例。对于第 $1$ 个测试用例：

• 初始棋子分布为 $(0, 1, 0, 0, 1, 1, 0, 1)$
• 通过以下 $3$ 次操作可达成目标：
  1. 选择 $i = 5$，分布变为 $(0, 0, 1, 0, 2, 0, 1, 0)$
  2. 选择 $i = 8$，分布变为 $(0, 0, 0, 1, 0, 2, 0, 1)$
  3. 选择 $i = 8$，分布变为 $(0, 0, 0, 0, 1, 0, 2, 1)$
• 无法在少于 $3$ 次操作内达成目标，因此输出 $3$

对于第 $2$ 个测试用例，无论如何操作都无法满足条件，因此输出 -1。

翻译由 DeepSeek R1 完成