Условие задачи

Сяо Ай хочет освоить метод «разделяй и властвуй» применительно к умножению. Она сформулировала свою стратегию в виде следующей задачи:

Дан целевой набор $T$, являющийся подмножеством $\{1,\dots,n\}$ ($1\leq n\leq 5\times 10^5$). Вам необходимо сконструировать набор $T$ с помощью последовательности операций. Доступны следующие три типа операций:

• Создать набор размера один: $|S|=1$.
• Объединить два уже сконструированных непересекающихся набора $A$ и $B$, получив $A\cup B$.
• Сдвинуть уже сконструированный набор $A$, получив $A+x = \{ a+x : a\in A \}$.

Один и тот же сконструированный набор можно использовать в дальнейшем несколько раз. Вы должны гарантировать, что все наборы, возникающие в процессе операций, являются подмножествами $\{1,\dots,n\}$.

Ваша стоимость — это сумма размеров всех сконструированных наборов. Вам не нужно минимизировать стоимость, достаточно, чтобы она не превышала $5\times 10^6$. Количество использованных операций также не должно превышать $10^6$.

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

Первая строка содержит целое положительное число $n$.

Следующая строка содержит строку из 01 длиной $n$. Если $x$-й символ равен 1, то $x\in T$, иначе $x\notin T$. Гарантируется, что $T$ не пусто.

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

Первая строка должна содержать целое положительное число $m$ — количество выполненных вами операций.

Далее следуют $m$ строк, каждая из которых описывает операцию. Пусть $T_i$ — набор, полученный в результате $i$-й операции:

• 1 x — создание набора размера один $\{x\}$.
• 2 x y — объединение непересекающихся наборов $T_x$ и $T_y$.
• 3 x y — сдвиг уже сконструированного набора $T_x$ на $y$, то есть $T_x+y$.

Вы должны гарантировать, что все операции соответствуют требованиям задачи, а набор, полученный в результате последней операции, совпадает с $T$.

Примеры

Пример 1

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

5
11011

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

5
1 1
1 4
2 1 2
3 3 1
2 3 4

Примечание

• Первая операция: создание набора $T_1=\{1\}$.
• Вторая операция: создание набора $T_2=\{4\}$.
• Третья операция: объединение $T_1$ и $T_2$, получение $T_3=\{1,4\}$.
• Четвертая операция: сдвиг $T_3$ на $1$, получение $T_4=\{2,5\}$.
• Пятая операция: объединение $T_3$ и $T_4$, получение $T_5=\{1,2,4,5\}$. Это и есть искомый набор $T$.

Общая стоимость этого решения составляет $1 + 1 + 2 + 2 + 4 = 10$.

Подсказка

Если ваш алгоритм эффективен, не беспокойтесь о константах.