Problem Description

In a 3-dimensional space (the $xyz$ space), there are $N$ cones floating without overlapping each other.

Each cone has its base parallel to the $yz$ plane and is pointed in the positive $x$ direction.

The $i$-th cone has its base center at the $x$ coordinate $X_i$ with a radius of $R_i$ and a height of $H_i$.

Answer the following queries $Q$ times:

• Given two integers $A$ and $B$, find the volume of the part of the space where $A \leq x \leq B$ that lies inside any of the cones.

Input Format

The input is given from the standard input in the following format:

$N$ $Q$ $X_1$ $R_1$ $H_1$ $X_2$ $R_2$ $H_2$ : $X_N$ $R_N$ $H_N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_Q$ $B_Q$

• The first line contains the number of cones $N$ and the number of queries $Q$, separated by spaces.
• The next $N$ lines contain the $x$ coordinate of the base center $X_i$, the radius $R_i$, and the height $H_i$ of the $i$-th cone, separated by spaces.
• The next $Q$ lines contain the integers $A_i$ and $B_i$ representing the $i$-th query, separated by spaces.

Output Format

The output consists of $Q$ lines. The $i$-th line should contain the answer to the $i$-th query. The output is accepted if the absolute or relative error is within $10^{-3}$. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

10 10
3 3 3
2 1 1
5 2 3
1 5 6
2 9 3
4 6 12
11 18 5
4 15 25
0 2 3
1 1 7
0 1
0 2
0 10
3 10
0 100
3 8
1 5
2 9
3 4
6 9

Sample Output #1

8.843002
80.992182
4173.878112
3865.997282
8512.668894
2882.971997
1227.377293
3629.490541
114.081013
1747.545749

Sample Input #2

5 5
5 10 10
4 100 100
3 1000 1000
2 1000 1000
1 1000 1000
0 3
2 1000
4 314
3 217
5 432

Sample Output #2

9409079.422279
3139502408.531295
2100737789.465234
1613523459.243475
2532621914.444282

Notes/Hints

Constraints

• All given numbers are integers.
• $1 \leq N \leq 100$
• $1 \leq Q \leq 10^5$
• $0 \leq X_i \leq 10^4$
• $1 \leq H_i \leq 10^4$
• $1 \leq R_i \leq 10^3$
• $0 \leq A_i \leq B_i \leq 2 \times 10^4$

见题面 Input 部分

见题面 Output 部分