У вас есть две бинарные строки \(a\) и \(b\) длины \(n\). Вы хотите сделать все элементы обеих строк равными \(0\). К сожалению, вы можете изменять содержимое этих строк, используя только следующую операцию:
- Вы выбираете два индекса \(l\) и \(r\) (\(1 \le l \le r \le n\));
- Для каждого \(i\), соответствующего \(l \le i \le r\), заменить \(a_i\) на противоположное. То есть \(a_i := 1 - a_i\);
- Для каждого \(i\), удовлетворяющего либо \(1 \le i < l\), либо \(r < i \le n\), заменить \(b_i\) на противоположное. То есть \(b_i := 1 - b_i\).
Ваша задача — определить, возможно ли это, и если да, то найти такую подходящую последовательность операций. Количество операций не должно превышать \(n + 5\). Можно доказать, что если такая последовательность операций существует, то существует и последовательность с не более чем \(n + 5\) операциями.
Выходные данные
Для каждого набора входных данных выведите сначала «YES», если возможно сделать все элементы обеих строк равными \(0\). В противном случае выведите «NO». Если ответ «YES», в следующей строке выведите одно целое число \(k\) (\(0 \le k \le n + 5\)) — количество операций. Далее должны следовать \(k\) строк, каждая из которых содержит два целых числа \(l\) и \(r\) (\(1 \le l \le r \le n\)) — описание операции.
Если правильных ответов несколько, выведите любой из них.
Примечание
В первом наборе входных данных мы можем выполнить одну операцию с \(l = 2\) и \(r = 2\). Итак, \(a_2 := 1 - 1 = 0\) и строка \(a\) стала равной 000. \(b_1 := 1 - 1 = 0\), \(b_3 := 1 - 1 = 0\) и строка \(b\) стала равной 000.
Во втором и третьем наборах входных данных можно доказать, что невозможно сделать все элементы обеих строк равными \(0\).
В четвертом наборе входных данных мы можем выполнить операцию с \(l = 1\) и \(r = 2\), тогда строка \(a\) станет равной 01, а строка \(b\) не изменится. Затем выполняем операцию с \(l = 2\) и \(r = 2\), тогда \(a_2 := 1 - 1 = 0\) и \(b_1 = 1 - 1 = 0\). Итак, обе строки \(a\) и \(b\) стали равны 00.
В пятом наборе входных данных мы можем выполнить операцию с \(l = 1\) и \(r = 1\). Затем строка \(a\) стала равной 011, а строка \(b\) стала равной 100. Тогда мы можем выполнить операцию с \(l = 2\) и \(r = 3\), чтобы обе строки \(a\) и \(b\) стали равны 000.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
010
101
2
11
10
4
1000
0011
2
10
10
3
111
111
|
YES
1
2 2
NO
NO
YES
2
1 2
2 2
YES
2
1 1
2 3
|