409459: GYM103566 G Полив... <<Ой!>>

G. Полив... «Ой!»ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Алиса пишет компьютерную игру «Полив». В игре на клумбе растёт $$$n$$$ цветков в ряд, каждый из которых может быть полит или не полит. Таким образом, клумбу можно представить в виде массива $$$F$$$ из нулей и единиц длины $$$n$$$, где $$$F_i = 1$$$ означает, что цветок $$$i$$$ не полит, а $$$F_i = 0$$$ означает, что цветок $$$i$$$ полит.

За одну операцию игрок может выбрать позицию $$$i$$$ такую, что $$$F_i = 1$$$ и полить цветок $$$i$$$ (то есть $$$F_i$$$ станет равно $$$0$$$).

Пока Алиса писала код игры, она часто отвлекалась на общение со своим любимым преподавателем по программированию. Поэтому для неё большой неожиданностью стало то, что в какой-то момент времени (она не поняла, в какой именно) полив цветка стал «странным». Теперь, если полить цветок $$$i$$$, то несколько политых цветков слева и справа от цветка $$$i$$$ станут не политыми.

Более формально эту «странность» можно описать так: когда игрок выбирает позицию $$$i$$$ для которой $$$F_i = 1$$$, в программе Алисы выбираются какие-нибудь границы $$$l$$$ и $$$r$$$ ($$$1 \le l \le i \le r \le n$$$) при которых для любого $$$j \in [l, r]$$$ выполняется $$$F_j = 1 \Leftrightarrow j = i$$$ (то есть на отрезке $$$[l, r]$$$ все цветы политы, кроме цветка на позиции $$$i$$$). И после полива цветка $$$i$$$ этот цветок станет политым, а все остальные цветы на отрезке $$$[l, r]$$$ станут не политыми.

«Ой» — вскрикнула Алиса, как только заметила «странность». Конечно же, вместо того, чтобы исправить «странность», Алиса начала случайно выбирать цветы, поливать их и смотреть, как изменяется клумба. Спустя какое-то время Алиса заскучала, она остановилась на клумбе в состоянии $$$A$$$. Теперь ей стало интересно, можно ли из данного состояния получить состояние $$$B$$$. И если да, то как это может произойти.

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество цветов на клумбе.

Во второй строке записано состояние клумбы, которое есть на данный момент у Алисы — строка $$$A$$$ длины $$$n$$$, состоящая из нулей и единиц.

В третьей строке записано состояние клумбы, которое хочет получить Алиса — строка $$$B$$$ длины $$$n$$$, состоящая из нулей и единиц.

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

Если из состояния $$$A$$$ невозможно получить состояние $$$B$$$ за не более чем $$$4 \cdot n + 1$$$ полив, то в единственной строке выведите «NO» (без кавычек).

Если из состояния $$$A$$$ можно получить состояние $$$B$$$, то в первой строке выведите «YES» (без кавычек).

Во второй строке выведите $$$M$$$ ($$$M \le 4 \cdot n + 1$$$) — необходимое количество поливов, чтобы из состояния $$$A$$$ получить состояние $$$B$$$.

Обратите внимание, что минимизировать количество поливов $$$\textbf{не требуется}$$$.

В каждой из следующих $$$M$$$ строк выведите по 3 числа: $$$i \ l \ r$$$:

• $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) — отрезок, который должен быть выбран программой Алисы;
• $$$i$$$ ($$$l \le i \le r$$$) — номер цветка, который надо полить на выбранном отрезке. Цветок $$$i$$$ должен быть единственным не политым на отрезке $$$[l, r]$$$ ($$$F_j = 1 \Leftrightarrow j = i$$$ для $$$l \le j \le r$$$).

Если существует несколько возможных последовательностей поливов, преобразующих $$$A$$$ в $$$B$$$, то выведите любую из них.

ПримерВходные данные

10
1001010010
1110111110

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

YES
3
4 2 5
9 9 10
10 7 10

Примечание

Рассмотрим, как будет меняться строка после каждой операции в примере:

1. $$$1\underline{\textbf{0010}}10010 \rightarrow 1\underline{\textbf{1101}}10010$$$
2. $$$11101100\underline{\textbf{10}} \rightarrow 11101100\underline{\textbf{01}}$$$
3. $$$111011\underline{\textbf{0001}} \rightarrow 111011\underline{\textbf{1110}}$$$