Bajtazar 在 Bajtogród 经营着一家滑雪板租赁店。这是一项季节性生意，因为租滑雪板的游客数量很大程度上取决于天气。为了让生意盈利，Bajtazar 决定仔细计划什么时候开业和关店。

为此，他查看了接下来几天的降雪预报，并开始思考什么时候开店会比较合适。他发现，最好让租赁店连续营业若干天，并且营业天数应选择使得平均降雪量在营业期间达到最大。一切看起来很简单，但过了一会儿 Bajtazar 又看了一眼电脑屏幕，发现天气预报又变了。更糟的是，没过多久，他发现自己原本打算开店的那天有意外的客人来访，不得不更改计划。这让 Bajtazar 更加认真对待这件事，并渴望拥有一个能帮助他做计划的程序。

输入格式

输入的第一行包含两个整数 $ n $ 和 $ z $（$1 \le n , z \le 500,000$）。它们分别表示 Bajtazar 计划涉及的天数和发生的事件数。第二行包含 $ n $ 个整数 $ s_{i} $（$0 \le s_{i} \le 20,000,000$）。数 $ s_{i} $ 表示第 $ i $ 天（天从 1 到 $ n $ 编号）的预测降雪量（单位为毫米）。

接下来的 $ z $ 行中，每行描述一个事件。事件按时间顺序给出。事件描述以字母 $ t_{j} $ 开头（$ t\_{j}\in \{\texttt{P}, \texttt{Z}\}$）。如果 $ t_{j} = \texttt{P}$，则该行接下来有两个整数 $ d_{j} $ 和 $ p_{j} $（$1 \le d_{j} \le n $, $0 \le p_{j} \le 20,000,000$），表示第 $ d_{j} $ 天的天气预报被更新，从现在起预测该天的降雪量为 $ p_{j} $ 毫米。新的预报也可能与之前相同。如果 $ t_{j} = \texttt{Z}$，则该行接下来有一个整数 $ w_{j} $（$1 \le w_{j} \le n $），表示 Bajtazar 计划在第 $ w_{j} $ 天开店，他想知道从第 $ w_{j} $ 天起连续若干天中，如何选择区间使得平均降雪量最大。你可以假设输入数据中至少有一个 Z 类型的事件。

输出格式

你的程序应针对每个 Z 类型事件输出一行答案。对于每个事件，输出从第 $ w_{j} $ 天起，连续若干天中最大平均降雪量的结果，要求答案以最简分数的形式给出，先输出分子，然后是 /，再输出分母。分子和分母都应为自然数。所有答案的顺序应与输入中的查询顺序一致。

样例

输入

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

输出

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