AT_agc077_a [AGC077A] Reverse A…B

You are given strings $ X $ and $ Y $ of length $ N $ consisting of `A` and `B`. Let $ X_i $ denote the $ i $ -th character of $ X $ . Determine whether it is possible to make $ X $ equal to $ Y $ by performing the following operation between $ 0 $ and $ \left\lfloor \frac{N}{2} \right\rfloor $ times, inclusive. - Choose a pair of integers $ (l, r) $ such that $ 1\leq l < r \leq N $ , $ X_l= $ `A`, and $ X_r= $ `B`. Reverse the elements of $ X $ from the $ l $ -th to the $ r $ -th position. Here, "reversing the elements of $ X $ from the $ l $ -th to the $ r $ -th position" means simultaneously replacing $ X_l,X_{l+1},\ldots,X_{r-1},X_r $ with $ X_r,X_{r-1},\ldots,X_{l+1},X_l $ . If it is possible to make $ X $ equal to $ Y $ , output one such sequence of operations. $ T $ test cases are given; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ X $ $ Y $

Output the answers for $ \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T $ in this order in the following format. If it is impossible to make $ X $ equal to $ Y $ using between $ 0 $ and $ \left\lfloor \frac{N}{2} \right\rfloor $ operations, inclusive, output `No`. If it is possible, output a sequence of operations in the following format: > Yes $ K $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ \vdots $ $ l_K $ $ r_K $ Here $ K $ is the number of operations, and $ l_i, r_i $ are the integers $ l, r $ chosen in the $ i $ -th operation. These must satisfy the following: - $ 0 \leq K \leq \left\lfloor \frac{N}{2} \right\rfloor $ - $ 1 \leq l_i < r_i \leq N $ If there are multiple valid sequences of operations, any of them will be accepted.

### Sample Explanation 1 In the first test case, $ X_3= $ `A` and $ X_5= $ `B`, so we can perform the operation of reversing the elements of $ X $ from the $ 3 $ -rd to the $ 5 $ -th position. After this operation, $ X $ is `ABBAA`, which equals $ Y $ . In the second test case, it is impossible to make $ X $ equal to $ Y $ regardless of the operations performed. ### Constraints - $ 1 \leq T \leq 2.5\times 10^5 $ - $ 2 \leq N \leq 5\times 10^5 $ - The sum of $ N $ over all test cases is at most $ 5\times 10^5 $ . - $ X $ and $ Y $ are strings of length $ N $ consisting of `A` and `B`. - All input values are integers.