{"problem":{"name":"Magnets","description":{"content":"You are given two length-$N$ strings $A = A_1A_2 \\ldots A_N$ and $B = B_1B_2 \\ldots B_N$, each consisting of `0` and `1`. There are $N$ squares aligned in a row from left to right. For $i = 1, 2, \\ldo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc193_d"},"statements":[{"statement_type":"Markdown","content":"You are given two length-$N$ strings $A = A_1A_2 \\ldots A_N$ and $B = B_1B_2 \\ldots B_N$, each consisting of `0` and `1`.\nThere are $N$ squares aligned in a row from left to right. For $i = 1, 2, \\ldots, N$, the $i$\\-th square from the left is called square $i$. Initially, square $i$ contains a piece if $A_i = $ `1`, and no piece if $A_i = $ `0`.\nYou may repeat the following operation any number of times (possibly zero):\n\n*   Choose an integer $i$ between $1$ and $N$, inclusive.\n*   Move all pieces simultaneously one square closer to square $i$. That is, for each piece, let square $j$ be its current position and square $j'$ be its new position, and the following holds:\n    *   if $i < j$, then $j' = j-1$;\n    *   if $i > j$, then $j' = j+1$;\n    *   if $i = j$, then $j' = j$.\n\nDetermine whether it is possible to reach a configuration satisfying the following condition, and if it is possible, find the minimum number of operations needed to do so:\n\n> For every $i = 1, 2, \\ldots, N$, there is at least one piece in square $i$ if and only if $B_i = $ `1`.\n\nYou are given $T$ independent test cases. Print the answer for each of them.\n\n## Constraints\n\n*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $1 \\leq N \\leq 10^6$\n*   $T$ and $N$ are integers.\n*   $A$ and $B$ are strings of length $N$, each consisting of `0` and `1`.\n*   There exists $i$ such that $A_i = $ `1`.\n*   There exists $i$ such that $B_i = $ `1`.\n*   The sum of $N$ over all test cases is at most $10^6$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nHere, $\\mathrm{case}_i$ ($i=1,2,\\ldots,T$) denotes the $i$\\-th test case.\nEach test case is given in the following format:\n\n$N$\n$A$\n$B$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc193_d","tags":[],"sample_group":[["3\n8\n01001101\n00001011\n3\n010\n111\n20\n10100011011110101011\n00010001111101100000","3\n-1\n5\n\nThe input has three independent test cases.\nIn the first test case, initially, the sequence of the numbers of pieces in the squares is $(0, 1, 0, 0, 1, 1, 0, 1)$. By performing the operation three times as follows, you can satisfy the condition:\n\n*   Choose $i = 5$. After the operation, the configuration is $(0, 0, 1, 0, 2, 0, 1, 0)$.\n*   Choose $i = 8$. After the operation, the configuration is $(0, 0, 0, 1, 0, 2, 0, 1)$.\n*   Choose $i = 8$. After the operation, the configuration is $(0, 0, 0, 0, 1, 0, 2, 1)$.\n\nIt is impossible to satisfy the condition in fewer than three operations, so the answer is $3$.\nIn the second test case, no matter how you perform the operations, you cannot satisfy the condition, so the answer is `-1`."]],"created_at":"2026-03-03 11:01:14"}}