Treść zadania

Xiao Ai chce zmierzyć się z mnożeniem typu „dziel i zwyciężaj”. Sformalizowała swoją strategię w następujący problem:

Dany jest zbiór docelowy $T$, który jest podzbiorem $\{1,\dots,n\}$ ($1\leq n\leq 5\times 10^5$). Musisz skonstruować zbiór $T$ poprzez serię operacji. Dostępne są trzy rodzaje operacji:

• Utworzenie zbioru jednoelementowego $|S|=1$.
• Połączenie dwóch rozłącznych, już skonstruowanych zbiorów $A$ i $B$, otrzymując $A\cup B$.
• Przesunięcie już skonstruowanego zbioru $A$, czyli $A+x = \{ a+x : a\in A \}$.

Każdy skonstruowany zbiór może być użyty wielokrotnie w późniejszych operacjach. Musisz zapewnić, że wszystkie zbiory pojawiające się w trakcie operacji są podzbiorami $\{1,\dots,n\}$.

Twoim kosztem jest suma rozmiarów wszystkich skonstruowanych zbiorów. Nie musisz minimalizować tego kosztu; wystarczy, że nie przekroczy on $5\times 10^6$. Liczba wykonanych operacji nie powinna przekroczyć $10^6$.

Wejście

Pierwsza linia zawiera liczbę całkowitą dodatnią $n$.

Druga linia zawiera ciąg binarny o długości $n$. Jeśli $x$-ty znak jest równy 1, oznacza to, że $x\in T$, w przeciwnym razie $x\notin T$. Gwarantuje się, że $T$ jest niepusty.

Wyjście

W pierwszej linii wypisz liczbę całkowitą dodatnią $m$ oznaczającą liczbę wykonanych operacji.

W kolejnych $m$ liniach opisz operacje. Niech $T_i$ oznacza zbiór uzyskany w $i$-tej operacji:

• 1 x oznacza utworzenie zbioru $\{x\}$.
• 2 x y oznacza połączenie rozłącznych zbiorów $T_x$ i $T_y$.
• 3 x y oznacza przesunięcie już skonstruowanego zbioru $T_x$ o $y$, czyli $T_x+y$.

Musisz zapewnić, że wszystkie operacje spełniają wymagania zadania, a zbiór uzyskany w ostatniej operacji jest równy $T$.

Przykład

Wejście 1

5
11011

Wyjście 1

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

Uwagi

• Pierwsza operacja: utworzenie zbioru $T_1=\{1\}$.
• Druga operacja: utworzenie zbioru $T_2=\{4\}$.
• Trzecia operacja: połączenie $T_1$ i $T_2$, otrzymując $T_3=\{1,4\}$.
• Czwarta operacja: przesunięcie $T_3$ o $1$, otrzymując $T_4=\{2,5\}$.
• Piąta operacja: połączenie $T_3$ i $T_4$, otrzymując $T_5=\{1,2,4,5\}$. Jest to zbiór $T$.

Całkowity koszt tego rozwiązania wynosi $1 + 1 + 2 + 2 + 4 = 10$.

Wskazówki

Jeśli Twoja złożoność obliczeniowa jest odpowiednia, zaufaj stałym.