Background

Patchouli has a huge library with tens of thousands of books, most of which are magic books.

Problem Description

A magic book is a kind of book that requires a key to understand. However, only someone whose proficiency is equal to or higher than the author can see the key. Therefore, each magic book has its own level $a_i$, and it also has its own knowledge value $w_i$. Now we want to know how much knowledge a creature with level $b_i$ can gain from these magic books.

Unfortunately, each creature does not know its exact level, only an approximate range of levels. You need to compute the expected knowledge value that the creature can obtain.

Input Format

The first line contains two positive integers $n, m$, representing the initial number of books and the number of operations.

The next $n$ lines each contain two positive integers $a_i$ and $w_i$, representing the level and the knowledge value of each book.

The next $m$ lines each contain $2$ or $3$ positive integers.

Operation 1: Format: 1 x y. Meaning: query the expected knowledge value that a creature with level in $[x, y]$ can obtain.

Operation 2: Format: 2 x y. Meaning: the library acquires a new magic book with level $x$ and knowledge value $y$.

Output Format

Output several lines of real numbers, which are the results of all Operation 1 queries. Print each answer to four decimal places.

5 5
1 1
2 1
3 1
4 1
5 1
1 2 5
1 1 5
1 3 5
2 1 5
1 1 2

3.5000
3.0000
4.0000
6.5000

Hint

For $30\%$ of the testdata, it is guaranteed that $1 \le$ all input numbers $\le 10^3$.

For $100\%$ of the testdata, it is guaranteed that $1 \le n, m \le 10^5$. For the other numbers, they are guaranteed to be within the range of 32-bit signed integers (and all numbers during computation are guaranteed to be within $-2^{63} \sim 2^{63} - 1$).

Translated by ChatGPT 5