У вас есть две строки \(a\) и \(b\) равной длины \(n\), состоящие из символов 0 и 1, а также целое число \(k\).
Вам нужно сделать строки \(a\) и \(b\) равными.
За один шаг вы можете выбрать любую подстроку \(a\), содержащую ровно \(k\) символов 1 (и произвольное число символов 0), и перевернуть её. Формально, если \(a = a_1 a_2 \ldots a_n\), вы можете выбрать любые \(l\) и \(r\) (\(1 \le l \le r \le n\)) такие, что среди символов \(a_l, a_{l+1}, \ldots, a_r\) ровно \(k\) единиц, и сделать \(a\) равной \(a_1 a_2 \ldots a_{l-1} a_r a_{r-1} \ldots a_l a_{r+1} a_{r+2} \ldots a_n\).
Найдите способ сделать строки \(a\) и \(b\) равными, используя не более \(4n\) переворотов такого рода, или определите, что такого способа не существует. Минимизировать число переворотов не нужно.
Выходные данные
Для каждого набора входных данных, если невозможно сделать \(a\) и \(b\) равными, используя не более \(4n\) переворотов, выведите одно целое число \(-1\).
В противном случае выведите целое число \(m\) (\(0 \le m \le 4n\)) — число переворотов в вашей последовательности шагов, и \(m\) пар целых чисел \(l_i, r_i\) (\(1 \le l_i \le r_i \le n\)) — границы подстрок \(a\), которые нужно перевернуть, в хронологическом порядке. Каждая подстрока должна содержать ровно \(k\) единиц на момент переворота.
Обратите внимание, что \(m\) минимизировать не нужно. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных после первого переворота \(a = \) 011010, после второго переворота \(a = \) 010110, после третьего переворота \(a = \) 010101.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
6 1
101010
010101
6 3
101010
010101
6 0
101010
010101
6 6
101010
010101
4 2
0000
1111
9 2
011100101
101001011
|
3
1 2
3 4
5 6
1
1 6
-1
-1
-1
5
4 8
8 9
3 6
1 4
3 6
|