Problem description

Nadszedł czas, żeby oprócz rozwiązywania zadań algorytmicznych w stylu na czterowymiarowego dynamika po posortowaniu topologicznym rozwiązać wreszcie coś przydatnego w praktyce.

Algorytm LZ77 (od nazwisk autorów Lempel–Ziv i roku opracowania), a przynajmniej wariant algorytmu, który rozważamy w tym zadaniu, kompresuje strumień (np. napis) w następujący sposób:

• tekst T jest przetwarzany od lewej do prawej i dzielony na rozłączne bloki (spójne fragmenty tekstu), które pokrywają cały tekst T,
• jeśli przetworzono już pewien prefiks tekstu T[..i], jako następny blok wybierany jest najdłuższy prefiks T[i+1..], który występuje jako spójne podsłowo (niekoniecznie blok) rozpoczynające się na pozycji co najwyżej i, przedłużone o jeden znak (zauważ, że w szczególności dopuszczalne jest aby to podsłowo zawierało pozycję i + 1),
• przyjmujemy założenie, że po tekście występuje “niewidzialny” znak różny niż wszystkie inne znaki tekstu.

Przykładowo, jeżeli mamy do skompresowania napis abaababaab to algorytm może podzielić go na następujące bloki (zakładamy, że pozycje tekstu numerowane są od 0):

• a (do pustego podsłowa dopisujemy a),
• b (do pustego podsłowa dopisujemy b),
• aa (do słowa T[0..0] dopisujemy a),
• bab (do słowa T[1..2] dopisujemy a),
• aab (do słowa T[2..4] dopisujemy niewidzialny znak końca tekstu).

Tego typu kompresja używana jest (z różnymi modyfikacjami) w praktyce – np. w formacie zip. Tym razem nie ma żadnego Jasia, który nie wiedzieć dlaczego prosi Cię o pomoc. Jest przecież jasne i naturalne, że chciałoby się szybko kompresować długie teksty. Powodzenia!

Napisz program, który wczyta napis do skompresowania, wyznaczy jego postać LZ77 i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się napis do skompresowania składający się z małych liter alfabetu angielskiego.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna B – liczba bloków w kompresji LZ77. W kolejnych B wierszach należy podać opis kolejno występujących bloków. Opis każdego bloku składać się ma z dwóch liczb naturalnych S_i oraz E_i oddzielonych pojedynczym odstępem, określających pozycję początkową i końcową fragmentu tekstu, z którego składa się blok (pozycja S_i musi odpowiadać już opisanemu wcześniej na wyjściu fragmentowi tekstu z wejścia), pojedynczego odstępu oraz znaku C_i, który należy dopisać do tego fragmentu.

Pozycje w słowie numerujemy kolejnymi liczbami naturalnymi zaczynając od 0. Puste podsłowo oznaczamy S_i = E_i =  − 1. Niewidzialny znak końca tekstu oznaczamy $.

Ograniczenia

Długość napisu nie przekracza 1 000 000 znaków.

Przykład

abaababaab

5
-1 -1 a
-1 -1 b
0 0 a
1 2 b
2 4 $

aaaaababaaab

4
-1 -1 a
0 3 b
4 6 a
6 7 $