Description

The Y901 Expressway is an east–west chain consisting of $n-1$ road segments and $n$ toll stations. From west to east, we number the stations $1$ to $n$. Traveling from station $i$ to $i+1$ (or from $i+1$ to $i$) costs $v_i$. When the expressway was first built, all segments were free, i.e., all $v_i = 0$.

The authorities will, from time to time, adjust the toll standards for consecutive segments, increasing or decreasing them according to policy.

A bored student, "Xiao A" (pinyin: Xiao A), likes to ponder quirky questions. While driving on this expressway, he wondered: for given $l, r$, choose two distinct stations $a$ and $b$ uniformly at random from stations $l$ through $r$. What is the expected cost to travel from $a$ to $b$?

Input Format

The first line contains two integers $n$ and $m$, the number of toll stations and the total number of updates and queries.

Each of the next $m$ lines describes an update or a query and begins with a character $op$.

• If $op$ is C, then there follow three integers $l, r, v$, meaning: increase by $v$ the toll on every road segment between the $l$-th and the $r$-th stations (i.e., all segments with indices $i$ where $l \le i < r$).
• If $op$ is Q, then there follow two integers $l, r$. For the given $l, r$, answer Xiao A’s question.

Output Format

For each query, output a single line containing the answer as a reduced fraction.

If the answer is an integer $a$, output a/1.

4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4

1/1
8/3
17/6

Hint

Constraints

There are $10$ test points. The scale of each test point is as follows.

For all test points, it is guaranteed that $1 \le n, m \le 10^5$, $op \in \{\texttt{C}, \texttt{Q}\}$, $1 \le l \le r \le n$, $-10^4 \le v \le 10^4$, and at any time $0 \le v_i \le 10^4$.

Translated by ChatGPT 5