Prefix Flip Transformation - Repovive Premier Round 3 | Repovive

6C. Prefix Flip Transformation

1500 pts1s256 MB

Alice has two binary strings $S$ and $T$ of length $n$ . She has a special machine that, given an index $i$ where the current $S_i$ is $1$ , flips the entire prefix $S_1, S_2, \ldots, S_i$ (changing $0$ to $1$ and $1$ to $0$ ). She can use this operation multiple times. Determine if she can transform $S$ into $T$ using at most $n$ operations, and if so, output any valid sequence of operations.

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, output one of the following forms:

\left. \begin{array}{l} \texttt{Yes} \\ k \\ i_1 \; i_2 \; \ldots \; i_k \end{array} \quad \text{or} \quad \begin{array}{l} \texttt{No} \end{array} \right\} \times t

Here $k$ is the number of operations, $0 \le k \le n$ , and $1 \le i_j \le n$ for every $1 \le j \le k$ . The operation indices must be valid in the given order. If there are multiple valid answers, you may output any of them.

Samples

Input

Case 1

1
0
0

Case 2

1
0
1

Case 3

2
11
10

Case 4

5
10101
01100

Case 5

5
00001
00110

Explanation

Case 1

The two strings are already equal, so no operation is needed.

Case 2

It is impossible to perform any operation, because the only character of $S$ is $0$ . Therefore, $S$ cannot be changed into $T$ .

Case 3

The output uses $2$ operations.

First, choose $i=1$ . The current value of $S_1$ is $1$ , so the operation is valid.

11 \to 01

Then choose $i=2$ . The current value of $S_2$ is $1$ , so the operation is valid.

01 \to 10

Now $S$ is equal to $T$ .

Case 4

The output uses $3$ operations.

First, choose $i=5$ . The current value of $S_5$ is $1$ , so the operation is valid.

10101 \to 01010

Then choose $i=2$ . The current value of $S_2$ is $1$ , so the operation is valid.

01010 \to 10010

Then choose $i=4$ . The current value of $S_4$ is $1$ , so the operation is valid.

10010 \to 01100

Now $S$ is equal to $T$ .

Case 5

The output uses $2$ operations.

First, choose $i=5$ . The current value of $S_5$ is $1$ , so the operation is valid.

00001 \to 11110

Then choose $i=2$ . The current value of $S_2$ is now $1$ , so the operation is valid.

11110 \to 00110

Now $S$ is equal to $T$ .

Output

Case 1

Yes
0

Case 2

No

Case 3

Yes
2
1 2

Case 4

Yes
3
5 2 4

Case 5

Yes
2
5 2

$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, output one of the following forms:

\left. \begin{array}{l} \texttt{Yes} \\ k \\ i_1 \; i_2 \; \ldots \; i_k \end{array} \quad \text{or} \quad \begin{array}{l} \texttt{No} \end{array} \right\} \times t

It is impossible to perform any operation, because the only character of $S$ is $0$ . Therefore, $S$ cannot be changed into $T$ .

The output uses $2$ operations.

First, choose $i=1$ . The current value of $S_1$ is $1$ , so the operation is valid.

11 \to 01

Then choose $i=2$ . The current value of $S_2$ is $1$ , so the operation is valid.

01 \to 10

Now $S$ is equal to $T$ .

The output uses $3$ operations.

First, choose $i=5$ . The current value of $S_5$ is $1$ , so the operation is valid.

10101 \to 01010

Then choose $i=2$ . The current value of $S_2$ is $1$ , so the operation is valid.

01010 \to 10010

Then choose $i=4$ . The current value of $S_4$ is $1$ , so the operation is valid.

10010 \to 01100

Now $S$ is equal to $T$ .

The output uses $2$ operations.

First, choose $i=5$ . The current value of $S_5$ is $1$ , so the operation is valid.

00001 \to 11110

Then choose $i=2$ . The current value of $S_2$ is now $1$ , so the operation is valid.

11110 \to 00110

Now $S$ is equal to $T$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

6C. Prefix Flip Transformation

Constraints

Input

Output

Samples

6C. Prefix Flip Transformation

Constraints

Input

Output

Samples