Ancient Sequence Table Updates

In the OI (Olympiad in Informatics) community, the legendary problem setter Hu Ce is famous for solving problems in an instant. Today, Hu Ce challenges you with an ancient sequence problem.

The ancient sequence \(a_0, a_1, a_2, \dots\) is defined by a recurrence relation. For all \(i>1\), it satisfies \[ 25\,a_i + 20\,a_{i-1} = 12\,a_{i-2}, \] with the additional property that \(a_i \ge 0\) for all \(i \ge 0\). Although the original values \(a_0\) and \(a_1\) have been lost to time, it is known that for any positive number \(t\), if \(a_0=t\) then the sequence \(a\) is uniquely determined.

A little analysis shows that the unique nonnegative solution is given by \[ a_i = t\,(0.4)^i,\] for all \(i \ge 0\) (since the characteristic equation \(25r^2+20r-12=0\) has roots \(r=0.4\) and \(r=-1.2\), and nonnegativity forces the coefficient of \((-1.2)^i\) to be zero).

You are given a table with n cells (numbered 1 through n), each initially holding the value 0. Hu Ce will issue two types of instructions:

• Update Query: The instruction is given in the format: 1 t p l r. This means that with the sequence defined by \(a_0=t\) (and hence \(a_i=t\,(0.4)^i\)), you must write the values \(a_{p}, a_{p+1}, \dots, a_{p+(r-l)}\) into the table cells numbered \(l, l+1, \dots, r\) (overwriting any previous values).
• Sum Query: The instruction is given in the format: 2 l r. Respond immediately with the sum of the values in the table from cell \(l\) to cell \(r\) (inclusive). Print the answer as a real number with 6 decimal places.

The input begins with two integers n and q denoting the number of cells and the number of queries. The following q lines each contain an instruction as described above. It is guaranteed that all indices and parameters are valid and that the value of t in update queries is a positive number.

Note: Due to the ancient nature of the problem and limited memory of the computer (64 MB), an efficient implementation is required.

inputFormat

The first line contains two integers n and q — the number of cells in the table and the number of queries, respectively.

Each of the next q lines contains a query in one of the following two formats:

• 1 t p l r — an update query. Here, t (a positive number) is used to define the sequence \(a_i = t\,(0.4)^i\). You must update the table cells from index l to r (inclusive) with the values \(a_{p}, a_{p+1}, \dots, a_{p+(r-l)}\) respectively.
• 2 l r — a sum query. Output the sum of values in table cells from index l to r (inclusive). The result should be printed with 6 decimal places.

outputFormat

For each sum query (query of type 2), print a line containing the resulting sum with exactly 6 decimal places.

sample

5 4
1 100 0 2 4
2 1 5
1 50 2 3 5
2 3 5

156.000000
12.480000