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.