#GYM104743D1. Prefix XOR Problem(Easy Version)
Prefix XOR Problem(Easy Version)
本题没有可用的提交语言。
Description
This is the easy version of this problem.The only difference is that you can perform at most $3n$ operations.
You are given two binary strings $a$ and $b$ of the same length $n$.
You can perform the following operation:
- choose an index $i$ ($1 \le i \le n$) and make $a_i := a_1 \oplus a_2 \oplus \ldots \oplus a_i$, where $\oplus$ denotes bitwise XOR.
Output any scheme to transform $a$ into $b$ by performing at most $3n$ operations.If there's no such scheme,output $-1$ instead.
The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
The second line contains the binary string $a$ of length $n$.
The third line contains the binary string $b$ of length $n$.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case, if it is impossible to transform $a$ into $b$ by performing such operations, output $-1$.
Otherwise, output $2$ lines.
The first line should contain a single integer $m$ ($0 \le m \le 3 \cdot n$) — the number of operations.
The second line should contain $m$ integers ($1 \le i_1, i_2, \ldots, i_m \le n$) — indices defining the operations.
It is guaranteed that if there is a way to transform $a$ into $b$, then it can be done in at most $3 \cdot n$ operations.
Input
The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
The second line contains the binary string $a$ of length $n$.
The third line contains the binary string $b$ of length $n$.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, if it is impossible to transform $a$ into $b$ by performing such operations, output $-1$.
Otherwise, output $2$ lines.
The first line should contain a single integer $m$ ($0 \le m \le 3 \cdot n$) — the number of operations.
The second line should contain $m$ integers ($1 \le i_1, i_2, \ldots, i_m \le n$) — indices defining the operations.
It is guaranteed that if there is a way to transform $a$ into $b$, then it can be done in at most $3 \cdot n$ operations.
4
2
01
00
2
00
00
4
1010
1101
6
110000
111111
-1
0
3
3 4 2
6
2 6 5 4 3 2