Migrated from Lutece 416 Balanced_Point

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Creating the stars is a boring job, the God also felt boring to do that. To make the creating more interesting, when created a star which had a mass value, the God put it at a position of a line. After created some stars, the God noticed that the he forgot where the mass central of the stars was. It was very important to know the mass central because the God needed to balance the mass. The God was very nervous. So, can you help the God with his problem? We assume there were no stars on the line at the beginning, and the universe was full of dust, whose mass is much lighter than a star and we can ignore it when compared with stars.

Input

There are several test cases and the input end with the end of file. In each case, the first line contains the length of the line $L$ ($1\leq L\leq 100000$) and the God’s action number $Q$ ($1\leq Q\leq 100000$); following $Q$ lines, the first integer in each line is $0$ or $1$, if the integer is $0$, and then follows $2$ integers $x, y$, ($1\leq x\leq y\leq L$) that indicate a query between $x$ and $y$, and you should output the mass central between the $x$ and $y$ of that time; if the integer is $1$, and then follow $2$ integers $p, v$, ($1\leq p\leq L$, $1\leq v\leq 100$) that indicate the God puts a star whose mass is $v$ in the position $p$.

Output

For every query, output a line contains only one number indicates where the mass central is. The output should round to $2$ digits after decimal.

Samples

3 4
1 2 3
0 1 3
1 3 3
0 1 3

2.00
2.50

Resources

5th BUPT Programming Contest Preliminary