Expected Toll Cost on a Highway

The highway consists of n toll stations in a row (numbered 1 to n) connected by n-1 road segments. The toll fee for the segment connecting station i and station i+1 is denoted by \(v_i\). Initially all segments are free (i.e. \(v_i=0\) for all valid i).

Over time, the government adjusts the toll fees on consecutive road segments. There are two types of operations:

• Update Operation: Given values l, r and d, increase the toll fee \(v_i\) by d for all segments with indices \(l \le i \lt r\).
• Query Operation: Given l and r (with \(l<r\)), two distinct toll stations are chosen uniformly at random among stations \(l, l+1, \dots, r\). If a car travels from the station with the lower number to the other one, the cost incurred is the sum of the tolls along the segments between them. The problem is to compute the expected cost for the travel.

Note: When computing the expected cost over all \(\binom{k}{2}\) pairs (where \(k = r-l+1\)), the contribution of segment \(i\) (for \(l \le i \lt r\)) is \(v_i \times (i-l+1) \times (r-i)\) because there are exactly \((i-l+1)\times (r-i)\) pairs whose path includes the segment \(i\). Thus, the expected cost is given by: \[ E = \frac{\sum_{i=l}^{r-1} v_i (i-l+1)(r-i)}{\binom{r-l+1}{2}}. \]

inputFormat

The first line contains two integers n and q (\(2 \le n \le \text{small}\), q is the number of operations).

Each of the following q lines represents an operation in one of the following formats:

• C l r d — Update operation: for every segment index \(i\) with \(l \le i < r\), increase \(v_i\) by d (\(|d|\) can be any integer).
• Q l r — Query operation: for stations l and r (where \(l < r\)), compute the expected toll cost as described above.

It is guaranteed that in any query \(l < r\) holds.

outputFormat

For each query operation, output the expected toll cost as a floating point number with 6 decimal places.

sample

5 1
Q 1 5

0.000000