Palindromic Not - Repovive Standard Round 5 | Repovive

14E. Palindromic Not

2500 pts1s256 MB

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

In one operation, you choose two indices $l$ and $r$ such that $1 \le l < r \le n$ , and the substring $S_l S_{l+1} \ldots S_r$ is a palindrome. Then you invert every bit in this substring. In other words, every $0$ becomes $1$ , and every $1$ becomes $0$ .

You have to determine whether it is possible to transform $S$ into $T$ .

If it is possible, output any sequence of at most $n+10$ operations that transforms $S$ into $T$ .

Constraints

$1 \le t \le 100$
$1 \le n \le 2000$
$S$ and $T$ are binary strings of length $n$

Input

The first line contains an integer $t$ , the number of test cases.

Then the test cases are given in the following format:

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:

\texttt{No}

Otherwise, output:

\begin{array}{l} \texttt{Yes} \\ m \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_m \quad r_m \end{array}

Here $m$ is the number of operations, and it must satisfy $0 \le m \le n+10$ . For every $i$ , the segment $[l_i,r_i]$ must be valid at the moment when the $i$ -th operation is applied.

The words Yes and No must be printed exactly in this form. If there are several valid answers, output any of them.

Samples

Input

Case 1

5
01010
10101

Explanation

The chosen substring from positions 1 to 5 is 01010, which is a palindrome. After inverting it, the string becomes 10101, so it is equal to the target string.

Output

Yes
1
1 5

Input

Case 1

3
000
010

Case 2

4
0101
0000

Case 3

5
11100
00111

Explanation

Case 1

It is impossible.

Case 2

0101 becomes 1011, then 1000, then 1111, and finally 0000.

Case 3

11100 becomes 00000, then 00111.

Output

Case 1

No

Case 2

Case 3

Yes
2
1 3
3 5

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

You have to determine whether it is possible to transform $S$ into $T$ .

If it is possible, output any sequence of at most $n+10$ operations that transforms $S$ into $T$ .

$1 \le t \le 100$
$1 \le n \le 2000$
$S$ and $T$ are binary strings of length $n$

The first line contains an integer $t$ , the number of test cases.

Then the test cases are given in the following format:

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:

\texttt{No}

Otherwise, output:

\begin{array}{l} \texttt{Yes} \\ m \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_m \quad r_m \end{array}

Here $m$ is the number of operations, and it must satisfy $0 \le m \le n+10$ . For every $i$ , the segment $[l_i,r_i]$ must be valid at the moment when the $i$ -th operation is applied.

The words Yes and No must be printed exactly in this form. If there are several valid answers, output any of them.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

14E. Palindromic Not

Constraints

Input

Output

Samples

14E. Palindromic Not

Constraints

Input

Output

Samples