Wypożyczalnia nart [A]
Limit pamięci: 128 MB
Bajtazar prowadzi w Bajtogrodzie wypożyczalnię nart.
Jest to biznes sezonowy, bo liczba turystów wypożyczających narty mocno zależy od pogody.
Żeby interes się opłacał, Bajtazar postanowił starannie zaplanować, kiedy otworzy i zamknie wypożyczalnię.
W tym celu sprawdził prognozowane opady śniegu w ciągu najbliższych dni i zaczął się zastanawiać, kiedy
byłoby mu wygodnie otworzyć wypożyczalnię.
Stwierdził, że najlepiej, by wypożyczalnia była czynna przez pewną liczbę kolejnych dni, a długość
działania wypożyczalni była dobrana tak, by średnie opady śniegu w czasie otwarcia wypożyczalni były jak największe.
Wszystko wydawało się proste, jednak po chwili Bajtazar znów zerknął na ekran komputera i okazało się,
że prognoza pogody zmieniła się.
Co gorsza, chwilę później okazało się, że w dniu, kiedy Bajtazar zamierzał otworzyć wypożyczalnię, przyjeżdżają
do niego niespodziewani goście i musi on zmienić plany.
To spowodowało, że Bajtazar podszedł do sprawy poważniej i zapragnął mieć program, który pomoże mu w planowaniu.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i ().
Oznaczają one liczbę dni objętych planami Bajtazara oraz liczbę zdarzeń, jakie miały miejsce.
W drugim wierszu znajduje się ciąg liczb całkowitych ().
Liczba to prognozowana wielkość opadów śniegu w trakcie -tego dnia (dni numerujemy kolejno od do ), w milimetrach.
W każdym z kolejnych wierszy znajduje się opis jednego zdarzenia.
Zdarzenia podane są w porządku chronologicznym.
Opis zdarzenia rozpoczyna się od litery ().
Jeśli , to w dalszej części wiersza znajdują się dwie liczby całkowite oraz
(, ).
Oznaczają one, że zaktualizowana została prognoza pogody na dzień i od teraz przewiduje ona opad milimetrów śniegu.
Może się zdarzyć, że nowa prognoza przewiduje takie same opady, jak poprzednia.
Jeśli zaś , to w dalszej części wiersza znajduje się jedna liczba całkowita ().
Oznacza ona, że Bajtazar planuje otworzyć wypożyczalnię w dniu numer i chciałby wiedzieć, jaki jest największy
możliwy średni opad śniegu w trakcie pewnego odcinka czasu, który zaczyna się w dniu .
Możesz założyć, że w danych wejściowych występuje co najmniej jedno zdarzenie typu Z.
Wyjście
Twój program powinien wypisać na wyjście po jednym wierszu z odpowiedzią dla każdego zdarzenia typu Z.
Odpowiedzią dla jednego zdarzenia jest średni opad śniegu w trakcie działania wypożyczalni, jeśli wypożyczalnia
zaczęłaby działanie w dniu i działała przez pewną liczbę kolejnych dni dobranych tak, by średni opad śniegu był jak największy.
Wynik należy podać w postaci ułamka zwykłego nieskracalnego, wypisując najpierw licznik, następnie znak /, a po nim mianownik.
Licznik i mianownik powinny być liczbami naturalnymi.
Odpowiedzi powinny być podane w kolejności zgodnej z kolejnością zapytań w wejściu.
Przykład
Dla danych wejściowych:
6 8
2 7 3 0 5 6
Z 2
Z 3
P 3 5
Z 1
Z 5
P 4 17
Z 2
Z 4
poprawną odpowiedzią jest:
7/1
7/2
14/3
11/2
29/3
17/1
Autorzy zadania: Jakub Łącki, Piotr Sankowski.