Rocket

On the planet Diskretigravija, whose gravity behaves unlike the usual, the inhabitants tune and test how efficient their rockets are. They have built $N$ rockets and want each one to reach a given height while spending as little fuel as possible.

A rocket behaves as follows. As long as it still has fuel, every second it ejects exactly one unit of fuel and its vertical velocity changes by

$\left\lfloor \frac{K}{M+T} \right\rfloor - g$

where

• $K$ is that rocket's fuel quality,
• $M$ is the rocket's mass without fuel,
• $T$ is the amount of fuel left immediately after this one unit was ejected,
• $g$ is the planet's free-fall acceleration,
• $\lfloor x \rfloor$ is the floor of $x$. A negative velocity means the rocket is falling.

Each second the rocket moves by its current velocity, so its height changes by the current velocity every second. Once the fuel runs out, the velocity decreases by $g$ every second. The height a rocket reaches is the highest point of its flight.

For example, take $K = 19$, $g = 2$, $M = 3$ and a rocket that starts with $3$ units of fuel. At the start of the first second it ejects the first unit and for exactly one second rises with velocity $\left\lfloor \frac{19}{3+2} \right\rfloor - 2 = 1$. After that the velocity grows by $\left\lfloor \frac{19}{3+1} \right\rfloor - 2 = 2$ to $3$ units per second, and after burning the last unit of fuel it grows by $\left\lfloor \frac{19}{3+0} \right\rfloor - 2 = 4$ to $7$ units per second. With the fuel gone, the velocity now drops by $2$ each second, so in total the rocket climbs to a height of $1 + 3 + 7 + 5 + 3 + 1 = 20$.

Help the testers determine the least amount of fuel each rocket needs in order to reach its desired height.

The first line contains two integers: the number of rockets $N$ and the planet's free-fall acceleration $g$.

Each of the next $N$ lines describes one rocket. Line $i+1$ contains three integers $K_i$, $M_i$ and $H_i$ — the fuel quality, the mass, and the height that rocket $i$ must reach.

Output $N$ lines, one integer each. On line $i$ print the smallest amount of fuel with which rocket $i$ can rise to a height of at least $H_i$, or $-1$ if that is impossible.

• $1 \le g$
• $1 \le M_i \le K_i \le 10^8$
• $1 \le H_i \le 10^{18}$
• $1 \le N \le 200$