highgarden-1

Princess Daenerys has now arrived at the Kingdom of  Reach. The ruler, Mace Tyrell invites her to the regional capital city, Highgarden. He agrees to surrender the kingdom without war, if she can win the game proposed by him. 

Mace Tyrell has planted several beautiful flowers in his gardens. Both of them are strolling in the garden and have stopped for a glass of wine. Each flower is at a particular distance from them right now and there is a cost associated with the maintenance of each planted flower. 

A flower F is said to be "more beautiful" than another flower G if it's distance is less than or equal to distance of flower G and the maintenance cost of flower G is strictly greater than that of flower F. 

A flower H is said to be "ravishing" among a collection of flowers (say C) if no flower in collection C is "more beautiful" than H. 

An "exquisite" collection of flowers (say E) is a maximal sub-collection of C, such that each flower in E is "ravishing".

Now, Mace Tyrell starts the game. He asks Daenerys to count number of flowers forming an "Exquisite" collection. Daenerys cannot count flowers lying beyond a particular distance (maxDist) and she can only choose flowers having maintenance cost less than or equal to maxCost (since she cannot afford more costly flowers) and no lesser than minCost (due to her Ego problems).  

The game has Q rounds. In each round, Daenerys is given three values - maxDist, minCost, maxCost and she has to  count the number of flowers forming an "Exquisite" collection with these constraints. 

Help Daenerys win the Kingdom.

Input

The first line contains an integer N, the number of flowers in the Garden.

The next N lines contain two integers D and C, denoting the distance and maintenance cost of the flower respectively.

The next line contains an integer Q, the number of rounds of the game.

The next Q lines contain three integers, denoting the values of maxDist, minCost and maxCost.

Output

Output Q lines containing a single integer which is the result for the corresponding round i.e. the no. of flowers forming the "Exquisite" collection.

Constraints

1 ≤ N ≤ 3 x 10^5

1 ≤ Q ≤ 2 x 10^5

0 ≤ D, C, maxDist, minCost, maxCost ≤ 10^9

Warning

Large input files. Use scanf/printf instead of cin/cout. Otherwise, use ios::sync_with_stdio(false).

SAMPLE INPUT
3
1 1
3 1
3 2
1
2 1 2

SAMPLE OUTPUT
1

Source: hackerearth | Difficulty: HARD


Solutions: