Bajtazar runs a ski rental shop in Bajtogród. It is a seasonal business, as the number of tourists renting skis depends heavily on the weather. To make the business profitable, Bajtazar decided to carefully plan when to open and close the rental shop.

To this end, he checked the snowfall forecast for the coming days and began to wonder when it would be convenient for him to open the shop. He concluded that it would be best for the shop to be open for a certain number of consecutive days, and the duration of the shop's operation should be chosen such that the average snowfall during the time the shop is open is as high as possible. Everything seemed simple, but after a while, Bajtazar looked at his computer screen again and found that the weather forecast had changed. Worse, a moment later, it turned out that unexpected guests were arriving on the day he intended to open the shop, and he had to change his plans. This caused Bajtazar to take the matter more seriously and he wanted a program that would help him with his planning.

Input

The first line of input contains two integers $n$ and $z$ ($1 \le n, z \le 500\,000$). They represent the number of days covered by Bajtazar's plans and the number of events that occurred. The second line contains a sequence of $n$ integers $s_{i}$ ($0 \le s_{i} \le 20\,000\,000$). The number $s_{i}$ is the forecasted amount of snowfall during the $i$-th day (days are numbered consecutively from 1 to $n$), in millimeters.

Each of the next $z$ lines contains a description of one event. The events are given in chronological order. The description of an event begins with a character $t_{j}$ ($t_{j} \in \{\texttt{P}, \texttt{Z}\}$). If $t_{j} = \texttt{P}$, the rest of the line contains two integers $d_{j}$ and $p_{j}$ ($1 \le d_{j} \le n$, $0 \le p_{j} \le 20\,000\,000$). They mean that the weather forecast for day $d_{j}$ has been updated and now predicts $p_{j}$ millimeters of snowfall. It may happen that the new forecast predicts the same snowfall as the previous one. If $t_{j} = \texttt{Z}$, the rest of the line contains one integer $w_{j}$ ($1 \le w_{j} \le n$). It means that Bajtazar plans to open the rental shop on day $w_{j}$ and would like to know what the maximum possible average snowfall is during some time interval that starts on day $w_{j}$. You may assume that there is at least one event of type Z in the input.

Output

Your program should output one line with the answer for each event of type Z. The answer for one event is the average snowfall during the shop's operation if the shop were to start operating on day $w_{j}$ and operate for a certain number of consecutive days chosen so that the average snowfall is as high as possible. The result should be given as an irreducible fraction, printing the numerator first, then the / character, and then the denominator. The numerator and denominator should be natural numbers. The answers should be provided in the order corresponding to the queries in the input.

Examples

Input 1

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

Output 1

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