C. Дополненный XOR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть две бинарные строки $$$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$$$ операциями.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длину строк.

Вторая строка каждого набора входных данных содержит бинарную строку $$$a$$$, состоящую только из символов 0 и 1, длины $$$n$$$.

Третья строка каждого набора входных данных содержит бинарную строку $$$b$$$, состоящую только из символов 0 и 1, длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите сначала «YES», если возможно сделать все элементы обеих строк равными $$$0$$$. В противном случае выведите «NO». Если ответ «YES», в следующей строке выведите одно целое число $$$k$$$ ($$$0 \le k \le n + 5$$$) — количество операций. Далее должны следовать $$$k$$$ строк, каждая из которых содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — описание операции.

Если правильных ответов несколько, выведите любой из них.

Пример
Входные данные
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
Примечание

В первом наборе входных данных мы можем выполнить одну операцию с $$$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.