CF1657D.For Gamers. By Gamers.

Monocarp is playing a strategy game. In the game, he recruits a squad to fight monsters. Before each battle, Monocarp has $C$ coins to spend on his squad.

Before each battle starts, his squad is empty. Monocarp chooses one type of units and recruits no more units of that type than he can recruit with $C$ coins.

There are $n$ types of units. Every unit type has three parameters:

• $c_i$ — the cost of recruiting one unit of the $i$-th type;
• $d_i$ — the damage that one unit of the $i$-th type deals in a second;
• $h_i$ — the amount of health of one unit of the $i$-th type.

Monocarp has to face $m$ monsters. Every monster has two parameters:

• $D_j$ — the damage that the $j$-th monster deals in a second;
• $H_j$ — the amount of health the $j$-th monster has.

Monocarp has to fight only the $j$-th monster during the $j$-th battle. He wants all his recruited units to stay alive. Both Monocarp's squad and the monster attack continuously (not once per second) and at the same time. Thus, Monocarp wins the battle if and only if his squad kills the monster strictly faster than the monster kills one of his units. The time is compared with no rounding.

For each monster, Monocarp wants to know the minimum amount of coins he has to spend to kill that monster. If this amount is greater than $C$, then report that it's impossible to kill that monster.

Monocarp 正在玩一款策略游戏。在游戏中，他招募一支小队来对抗怪物。每次战斗前，Monocarp 有 $C$ 枚金币可用于组建小队。

每次战斗开始前，他的小队为空。Monocarp 选择一种单位类型，并招募该类型的单位，数量不超过用 $C$ 枚金币所能招募的最大数量。

共有 $n$ 种单位类型。每种单位类型具有三个参数：

• $c_i$ —— 招募一个第 $i$ 类单位所需的金币数；
• $d_i$ —— 一个第 $i$ 类单位每秒造成的伤害；
• $h_i$ —— 一个第 $i$ 类单位的生命值。

Monocarp 需要面对 $m$ 只怪物。每只怪物具有两个参数：

• $D_j$ —— 第 $j$ 只怪物每秒造成的伤害；
• $H_j$ —— 第 $j$ 只怪物的生命值。

Monocarp 在第 $j$ 场战斗中仅需对抗第 $j$ 只怪物。他希望所有已招募的单位均存活至战斗结束。Monocarp 的小队与怪物持续（而非每秒一次）且同时进行攻击。因此，Monocarp 获胜当且仅当他所招募的小队击杀怪物所用的时间严格小于怪物击杀其任意一个单位所用的时间。时间比较不作任何舍入处理。

对于每只怪物，Monocarp 想知道击杀该怪物所需的最少金币数。若该金币数大于 $C$，则报告无法击杀该怪物。

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}$).

第一行包含两个整数 $n$ 和 $C$（$1 \le n \le 3 \cdot 10^5$；$1 \le C \le 10^6$）—— 分别表示单位种类数以及 Monocarp 每场战斗前拥有的金币数量。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $c_i, d_i$ 和 $h_i$（$1 \le c_i \le C$；$1 \le d_i, h_i \le 10^6$）。

下一行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$）—— 表示 Monocarp 需要面对的怪物数量。

接下来的 $m$ 行中，第 $j$ 行包含两个整数 $D_j$ 和 $H_j$（$1 \le D_j \le 10^6$；$1 \le H_j \le 10^{12}$）。

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$.

输出 $m$ 个整数。对于每个怪物，输出 Monocarp 杀死该怪物所需的最少金币数量。若该数量大于 $C$，则输出 $-1$。

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.

考虑第一个样例中的第一只怪物。

Monocarp 无法招募一个第一类单位，因为这将导致他与该怪物在 $0.75$ 秒内互相击杀。他可以花费 $6$ 枚金币招募两个第一类单位，并在 $0.375$ 秒内击杀该怪物。

Monocarp 可以招募一个第二类单位，因为他能在 $0.6$ 秒内击杀该怪物，而该怪物需要 $0.625$ 秒才能击杀他——该单位更快。因此，$5$ 枚金币即足够。

Monocarp 至少需要三个第三类单位才能击杀第一只怪物，这将花费 $30$ 枚金币。

若 Monocarp 选择第二类单位并招募其中的一个，则花费的金币最少。