For Gamers. By Gamers.

Description:

Input:

The first line contains two integers $$$n$$$ and $$$C$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le C \le 10^6$$$) — the number of types of units and the amount of coins Monocarp has before each battle.

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$c_i, d_i$$$ and $$$h_i$$$ ($$$1 \le c_i \le C$$$; $$$1 \le d_i, h_i \le 10^6$$$).

The next line contains a single integer $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — the number of monsters that Monocarp has to face.

The $$$j$$$-th of the next $$$m$$$ lines contains two integers $$$D_j$$$ and $$$H_j$$$ ($$$1 \le D_j \le 10^6$$$; $$$1 \le H_j \le 10^{12}$$$).

Output:

Print $$$m$$$ integers. For each monster, print the minimum amount of coins Monocarp has to spend to kill that monster. If this amount is greater than $$$C$$$, then print $$$-1$$$.

Sample Input:

3 10
3 4 6
5 5 5
10 3 4
3
8 3
5 4
10 15

Sample Output:

5 3 -1 

Sample Input:

5 15
14 10 3
9 2 2
10 4 3
7 3 5
4 3 1
6
11 2
1 1
4 7
2 1
1 14
3 3

Sample Output:

14 4 14 4 7 7 

Sample Input:

5 13
13 1 9
6 4 5
12 18 4
9 13 2
5 4 5
2
16 3
6 2

Sample Output:

12 5 

Note:

Consider the first monster of the first example.

Monocarp can't recruit one unit of the first type, because it will take both him and the monster $$$0.75$$$ seconds to kill each other. He can recruit two units for the cost of $$$6$$$ coins and kill the monster in $$$0.375$$$ second.

Monocarp can recruit one unit of the second type, because he kills the monster in $$$0.6$$$ seconds, and the monster kills him in $$$0.625$$$ seconds. The unit is faster. Thus, $$$5$$$ coins is enough.

Monocarp will need at least three units of the third type to kill the first monster, that will cost $$$30$$$ coins.

Monocarp will spend the least coins if he chooses the second type of units and recruits one unit of that type.