Flip 1...0 - Repovive Premier Round 4 | Repovive

9D. Flip 1...0

2000 pts2s256 MB

You are given two binary strings $S$ and $T$ , both of length $n$ .

In one operation, you may choose two indices $l$ and $r$ such that $1 \le l < r \le n$ , $S_l = 1$ , and $S_r = 0$ in the current string. Then you invert every bit in the segment $S_l, S_{l+1}, \ldots, S_r$ .

In other words, every $0$ in this segment becomes $1$ , and every $1$ becomes $0$ .

Your task is to transform $S$ into $T$ using at most $n$ operations, or determine that it is impossible.

If there are multiple valid answers, you may output any of them.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$S$ and $T$ are binary strings of length $n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ S \\ T \end{array} \right\} \times t

Output

For each test case, if it is impossible to transform $S$ into $T$ , output:

-1

Otherwise, output an integer $k$ , the number of operations.

Then output $k$ lines. In the $i$ -th line, output two integers $l_i$ and $r_i$ , meaning that the $i$ -th operation is applied to the segment $[l_i, r_i]$ .

The operations must be valid when they are applied, and after applying all operations the string must become equal to $T$ .

It must hold that $0 \le k \le n$ .

If there are multiple valid answers, you may output any of them.

Samples

Input

Case 1

4
1010
0001

Case 2

3
110
100

Case 3

5
01010
01010

Case 4

4
1100
0101

Case 5

6
111000
010101

Explanation

Case 1

After applying operation $[1,2]$ , the string becomes $0110$ . Then applying operation $[2,4]$ changes it to $0001$ .

Case 2

It is impossible to transform $110$ into $100$ using valid operations.

Case 3

The initial string is already equal to the target string, so no operation is needed.

Case 4

After applying operation $[2,3]$ , the string becomes $1010$ . Then applying operation $[1,4]$ changes it to $0101$ .

Case 5

After applying operation $[2,4]$ , the string becomes $100100$ . Then applying operation $[1,5]$ changes it to $011010$ . Finally, applying operation $[3,6]$ changes it to $010101$ .

Output

Case 1

2
1 2
2 4

Case 2

-1

Case 3

Case 4

2
2 3
1 4

Case 5

You are given two binary strings $S$ and $T$ , both of length $n$ .

In other words, every $0$ in this segment becomes $1$ , and every $1$ becomes $0$ .

Your task is to transform $S$ into $T$ using at most $n$ operations, or determine that it is impossible.

If there are multiple valid answers, you may output any of them.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$S$ and $T$ are binary strings of length $n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ S \\ T \end{array} \right\} \times t

For each test case, if it is impossible to transform $S$ into $T$ , output:

-1

Otherwise, output an integer $k$ , the number of operations.

Then output $k$ lines. In the $i$ -th line, output two integers $l_i$ and $r_i$ , meaning that the $i$ -th operation is applied to the segment $[l_i, r_i]$ .

The operations must be valid when they are applied, and after applying all operations the string must become equal to $T$ .

It must hold that $0 \le k \le n$ .

If there are multiple valid answers, you may output any of them.

After applying operation $[1,2]$ , the string becomes $0110$ . Then applying operation $[2,4]$ changes it to $0001$ .

It is impossible to transform $110$ into $100$ using valid operations.

After applying operation $[2,3]$ , the string becomes $1010$ . Then applying operation $[1,4]$ changes it to $0101$ .

After applying operation $[2,4]$ , the string becomes $100100$ . Then applying operation $[1,5]$ changes it to $011010$ . Finally, applying operation $[3,6]$ changes it to $010101$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

9D. Flip 1...0

Constraints

Input

Output

Samples

9D. Flip 1...0

Constraints

Input

Output

Samples