Problem H
Water Decor

The Pokemon Aquarium is finally remodeling! To commemorate its $5^{th}$ year anniversary, the Aquarium has built a massive water-based decoration!

The decoration is quite an interesting design and can be modeled as a series of non-overlapping circles in the square $(0, 0)$ to $(10^6, 10^6)$. For all integers $0 \leq x_ i \leq 10^6$, there exists a water dispenser at $(x_ i, \infty )$ that dispenses water directly downwards.

Water always flows directly downwards. If it hits a circle, it will flow differently depending on where it hits the circle.

1. If it hits the left half of the circle, it will flow along the left side and continue flowing downwards from the left half

2. If it hits the right half of the circle, it will flow along the right side and continue flowing downwards from the right half

3. If it hits the top of the circle, it will flow along both the left and right side of the circles and continue flowing downwards from both halves

Squirtle loves to watch the water flow in the decoration. He wonders, if all the water dispensers between $x = L$ to $x = R$ are activated, how many distinct $x$ coordinates will water reach at $y = 0$? Given $Q$ queries, please help Squirtle answer this puzzling question!

Input

The first line of input contains two integers, $N$ and $Q$. The next $N$ lines contain three integers $x_ i, y_ i, r_ i$, denoting a circle of radius $r_ i$ at $(x_ i, y_ i)$. The next $Q$ lines contain two integers $L_ j, R_ j$, denoting a query of water dispensers between $x = L_ j$ to $x = R_ j$ for the $j^{th}$ query.

$1 \leq N \leq 10^5$
$1 \leq Q \leq 2 \cdot 10^5$
$1 < x_ i, y_ i < 10^6$.
$1 \leq r_ i \leq 5 \cdot 10^5$
$0 \leq L_ j, R_ j \leq 10^6$

It is guaranteed all circles will be fully contained inside the square with a bottom-left corner at $(0, 0)$ and upper-right corner at $(10^6, 10^6)$, and all circles are non-intersecting.

Output

Output $Q$ integers, the $j^{th}$ of which is a single integer representing the number of distinct $x$ coordinates that water can flow to if the water dispensers from $x = L_ j$ to $x = R_ j$.

1 3
1 1 1
0 0
0 1
1 1

1
2
2

2 4
1 1 1
4 5 3
0 0
0 1
1 1
5 6

1
2
2
1