AT_arc193_d [ARC193D] Magnets

`0` と `1` のみからなる $ 2 $ つの長さ $ N $ の文字列 $ A = A_1A_2 \ldots A_N $ と $ B = B_1B_2 \ldots B_N $ が与えられます。 左右に一列に並んだ $ N $ 個のマスがあります。 $ i = 1, 2, \ldots, N $ について、左から $ i $ 番目のマスはマス $ i $ と呼ばれ、 はじめマス $ i $ には、 $ A_i $ = `1` ならばコマが $ 1 $ 個置かれており、 $ A_i $ = `0` ならばコマは置かれていません。 下記の操作を好きな回数（ $ 0 $ 回でも良い）だけ繰り返します。 - まず、 $ 1 $ 以上 $ N $ 以下の整数 $ i $ を選ぶ。 - そして、すべてのコマを同時に、マス $ i $ に近づく方向に $ 1 $ マス動かす。すなわち、各コマを次が成り立つように動かす： そのコマの移動前の位置をマス $ j $ 、移動後の位置をマス $ j' $ とすると、 - $ i \lt j $ ならば $ j' = j-1 $ 、 - $ i \gt 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 $ ここで、 $ i = 1, 2, \ldots, T $ について、 $ \mathrm{case}_i $ は $ i $ 番目のテストケースを表す。 各テストケースは下記の形式で与えられる。 > $ N $ $ A $ $ B $

$ T $ 行出力せよ。 $ i = 1, 2, \ldots, T $ について、 $ i $ 行目には $ i $ 番目のテストケースに対する答えとして、 問題文中の条件を満たす状態にすることが不可能な場合は `-1` を、 可能な場合はそれまでに操作を行う回数としてありえる最小値を出力せよ。

### Sample Explanation 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 $ 回未満の操作で問題文中の条件を満たす状態にすることはできないため、 $ 1 $ 番目のテストケースに対する答えとして、 $ 3 $ を出力します。 $ 2 $ 番目のテストケースでは、 どのような手順で操作を行っても、問題文中の条件を満たすことはできません。 よって、 $ 2 $ 番目のテストケースに対する答えとして、`-1` を出力します。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq N \leq 10^6 $ - $ T, N $ は整数 - $ A, B $ はそれぞれ `0` と `1` のみからなる長さ $ N $ の文字列 - $ A_i = $ `1` である $ i $ が存在する - $ B_i = $ `1` である $ i $ が存在する - すべてのテストケースにわたる $ N $ の総和は $ 10^6 $ 以下