8485번 - BARMAN 다국어

Profesor Bajtych jest bajtnistrem Arytmetycznych Rzędów Modulo Arbitralne N. Rzędem liczby a modulo n nazywamy najmniejsze takie m > 0, że a · m jest podzielne przez n. 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 k liczb a_i i n. Pracownik dostaje do swojej wiadomości jedynie rzędy a_i modulo n. Może on poprosić Bajtycha o wykonanie co najwyżej 2k operacji polegających na tym, że przemnaża się wszystkie liczby w pewnym spójnym podciągu a_i przez jakąś liczbę c. Bajtych płaci pracownikowi tyle B\$, ile wynosi rząd sumy a_i modulo n 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 n i a_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.

Napisz program, który:

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

W pierwszym wierszu podana jest jedna liczba 1 ≤ k ≤ 100. Drugi wiersz zawiera k liczb m_i, 1 ≤ m_i < 2⁶⁴. Liczba m_i jest rzędem a_i modulo n.

Wynikiem ma być opis ciągu operacji. W pierwszym wierszu ilość operacji p. W każdym z następnych p wierszy należy podać trzy liczby l_i, r_i i c_i, gdzie 1 ≤ c_i < 2⁶⁴. Oznaczają one, że i-ta operacja polega na pomnożeniu wszystkich liczb od a_li do a_ri przez c_i.