시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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 ai i n. Pracownik dostaje do swojej wiadomości jedynie rzędy ai 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 ai przez jakąś liczbę c. Bajtych płaci pracownikowi tyle B\$, ile wynosi rząd sumy ai 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 ai 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 mi, 1 ≤ mi < 264. Liczba mi jest rzędem ai 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 liri i ci, gdzie 1 ≤ ci < 264. Oznaczają one, że i-ta operacja polega na pomnożeniu wszystkich liczb od ali do ari przez ci.

예제 입력 1

3
6 10 15

예제 출력 1

3
2 3 6
1 1 5
3 3 5