BARMAN

Limit pamięci: 64 MB

Profesor Bajtych jest bajtnistrem Arytmetycznych Rzędów Modulo Arbitralne N. Rzędem liczby modulo nazywamy najmniejsze takie , że jest podzielne przez . Pracownicy Bajtnisterstwa zmuszeni są do grania w trudną grę w celu określenia ich pensji. Celem tej gry jest zapewnienie, by tylko osoby dobrze znające się na rzeczy zarabiały największe pieniądze.

Bajtych wybiera ciąg liczb i . Pracownik dostaje do swojej wiadomości jedynie rzędy modulo . Może on poprosić Bajtycha o wykonanie co najwyżej operacji polegających na tym, że przemnaża się wszystkie liczby w pewnym spójnym podciągu przez jakąś liczbę . Bajtych płaci pracownikowi tyle B$, ile wynosi rząd sumy modulo po wykonaniu wszystkich operacji.

Po kilku miesiącach urzędnicy BARMAN zorientowali się, że Bajtych jest bardzo zachłanny. W rzeczywistości wybiera on liczby i dopiero po tym, jak dostanie wszystkie operacje. Twoim zadaniem jest napisanie programu, który zasugeruje, jakie operacje należy wykonać, by Bajtych musiał nam zapłacić jak najwięcej.

Zadanie

Napisz program, który:

• wczyta opis ciągu ze standardowego wejścia,
• znajdzie optymalny ciąg operacji,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu podana jest jedna liczba . Drugi wiersz zawiera liczb , . Liczba jest rzędem modulo .

Wyjście

Wynikiem ma być opis ciągu operacji. W pierwszym wierszu ilość operacji . W każdym z następnych wierszy należy podać trzy liczby , i , gdzie . Oznaczają one, że -ta operacja polega na pomnożeniu wszystkich liczb od do przez .

Przykład

Dla danych wejściowych:

3
6 10 15

poprawną odpowiedzią jest:

3
2 3 6
1 1 5
3 3 5

Autor zadania: Jakub Pawlewicz.