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.

Input Format

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ n $ i $ z $ ($1 \le n , z \le 500\,000$). Oznaczają one liczbę dni objętych planami Bajtazara oraz liczbę zdarzeń, jakie miały miejsce. W drugim wierszu znajduje się ciąg $ n $ liczb całkowitych $ s_{i} $ ($0 \le s_{i} \le 20\,000\,000$). Liczba $ s_{i} $ to prognozowana wielkość opadów śniegu w trakcie $ i $-tego dnia (dni numerujemy kolejno od 1 do $ n $), w milimetrach.

W każdym z kolejnych $ z $ wierszy znajduje się opis jednego zdarzenia. Zdarzenia podane są w porządku chronologicznym. Opis zdarzenia rozpoczyna się od litery $ t_{j} $ ($ t_{j}\in \{\texttt{P}, \texttt{Z}\}$). Jeśli $ t_{j} = \texttt{P}$, to w dalszej części wiersza znajdują się dwie liczby całkowite $ d_{j} $ oraz $ p_{j} $ ($1 \le d_{j} \le n $, $0 \le p_{j} \le 20\,000\,000$,). Oznaczają one, że zaktualizowana została prognoza pogody na dzień $ d_{j} $ i od teraz przewiduje ona opad $ p_{j} $ milimetrów śniegu. Może się zdarzyć, że nowa prognoza przewiduje takie same opady, jak poprzednia. Jeśli zaś $ t_{j} = \texttt{Z}$, to w dalszej części wiersza znajduje się jedna liczba całkowita $ w_{j} $ ($1 \le w_{j} \le n $). Oznacza ona, że Bajtazar planuje otworzyć wypożyczalnię w dniu numer $ w_{j} $ i chciałby wiedzieć, jaki jest największy możliwy średni opad śniegu w trakcie pewnego odcinka czasu, który zaczyna się w dniu $ w_{j} $. Możesz założyć, że w danych wejściowych występuje co najmniej jedno zdarzenie typu Z.

Output Format

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 $ w_{j} $ 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.

Example

Input

6 8
2 7 3 0 5 6
With 2
With three
P 3 of 5
On the one
With 5
P 4 17
With 2
With 4

Output

7/1
7/2
14/3
11/2
29/3
17/1