스키 대여점

바이타자르는 바이토그로드에서 스키 대여점을 운영한다. 스키를 빌리는 관광객 수가 날씨에 크게 좌우되기 때문에 이 사업은 계절을 많이 탄다. 이익을 내려면 대여점을 언제 열고 닫을지 신중하게 계획해야 한다.

그는 앞으로 며칠 동안의 예상 강설량을 확인하고, 대여점을 며칠 동안 연속으로 운영하되 그 기간의 평균 강설량이 가능한 한 커지도록 운영 기간의 길이를 정하기로 했다. 하지만 일기 예보가 계속 바뀌고, 개장하려던 날에 갑자기 손님이 찾아오는 바람에 계획이 자주 틀어졌다. 그래서 그는 계획을 도와줄 프로그램을 원한다.

날짜별 예상 강설량과, 예보 갱신 이벤트 및 질의 이벤트의 열이 주어진다. 각 질의마다, 지정된 시작일부터 연속된 며칠을 운영할 때 얻을 수 있는 최대 평균 강설량을 구하라.

첫째 줄에 두 정수 $n$과 $z$가 주어진다 ($1 \le n, z \le 500\,000$). 각각 계획 대상 날짜 수와 이벤트 수이다. 둘째 줄에는 $n$개의 정수 $s_i$가 주어진다 ($0 \le s_i \le 20\,000\,000$). $s_i$는 $i$번째 날($1$부터 $n$까지 번호가 매겨진다)의 예상 강설량(밀리미터)이다.

다음 $z$개의 줄에는 각각 이벤트 하나가 시간 순서대로 주어진다. 각 이벤트는 문자 $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$). 바이타자르가 $w_j$번째 날에 대여점을 열려고 하며, $w_j$일에 시작하는 어떤 연속 기간에서의 최대 평균 강설량을 알고 싶다는 뜻이다.

입력에는 $\texttt{Z}$ 유형의 이벤트가 적어도 하나 있다고 가정해도 된다.

$\texttt{Z}$ 유형의 각 이벤트마다 한 줄씩 답을 출력한다. 답은 대여점이 $w_j$일에 문을 열어 평균 강설량이 최대가 되도록 며칠간 연속으로 운영할 때의 그 평균 강설량이다. 즉 $w_j \le k \le n$인 $k$에 대한 $\dfrac{s_{w_j} + s_{w_j+1} + \cdots + s_k}{k - w_j + 1}$의 최댓값이다.

답은 기약분수로, 분자, 문자 /, 분모 순서로 출력한다. 분자와 분모는 자연수여야 한다. 답은 입력에 등장한 질의 순서대로 출력한다.