can choose any substring of a containing exactly k characters 1 (and arbitrary number of characters 0) and reverse it. Formally, if a=a1a2…an, you can choose any integers l and r (1≤l≤r≤n) such that there are exactly k ones among characters al,al+1,…,ar, and set a to a1a2…al−1arar−1…alar+1ar+2…an.
Correct answer will be upvoted else downvoted.
you can choose any substring of a containing exactly k characters 1 (and arbitrary number of characters 0) and reverse it. Formally, if a=a1a2…an, you can choose any integers l and r (1≤l≤r≤n) such that there are exactly k ones among characters al,al+1,…,ar, and set a to a1a2…al−1arar−1…alar+1ar+2…an.
Find a way to make a equal to b using at most 4n reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤2000). Description of the test cases follows.
Each test case consists of three lines. The first line of each test case contains two integers n and k (1≤n≤2000; 0≤k≤n).
The second line contains string a of length n.
The third line contains string b of the same length. Both strings consist of characters 0 and 1.
It is guaranteed that the sum of n over all test cases does not exceed 2000.
Output
For each test case, if it's impossible to make a equal to b in at most 4n reversals, print a single integer −1.
Otherwise, print an integer m (0≤m≤4n), denoting the number of reversals in your sequence of steps, followed by m pairs of integers li,ri (1≤li≤ri≤n), denoting the boundaries of the substrings of a to be reversed, in chronological order. Each substring must contain exactly k ones at the moment of reversal.
Step by step
Solved in 3 steps with 1 images
