D. Для геймеров. От геймеров.
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в стратегическую игру. В игре он собирает отряд для борьбы с монстрами. Перед каждой битвой у Монокарпа есть $$$C$$$ монет, которые он может потратить на свой отряд.

Перед началом каждой битвы в его отряде никого нет. Монокарп выбирает один тип воинов и набирает не больше воинов этого типа, чем он может себе позволить за $$$C$$$ монет.

Существует $$$n$$$ типов воинов. Каждый тип воинов имеет три параметра:

  • $$$c_i$$$ — стоимость одного воина $$$i$$$-го типа;
  • $$$d_i$$$ — урон, который наносит один воин $$$i$$$-го типа за секунду;
  • $$$h_i$$$ — здоровье одного воина $$$i$$$-го типа.

Монокарпу придется сразиться с $$$m$$$ монстрами. У каждого монстра есть два параметра:

  • $$$D_j$$$ — урон, который наносит $$$j$$$-й монстр за секунду;
  • $$$H_j$$$ — здоровье $$$j$$$-го монстра.

Монокарп сражается только с $$$j$$$-м монстром во время $$$j$$$-й битвы. Он хочет, чтобы все его воины остались в живых. И отряд Монокарпа, и монстр атакуют одновременно и непрерывно. Таким образом, Монокарп выигрывает битву тогда и только тогда, когда его отряд убивает монстра строго быстрее, чем монстр убивает одного из его воинов. Время сравнивается без округления.

Для каждого монстра Монокарп хочет знать минимальное количество монет, которое он должен потратить, чтобы убить этого монстра. Если это количество больше, чем $$$C$$$, то сообщите, что убить этого монстра невозможно.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$C$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le C \le 10^6$$$) — количество типов воинов и количество монет у Монокарпа перед каждой битвой.

В $$$i$$$-й из следующих $$$n$$$ строк записаны три целых числа $$$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$$$) — количество монстров, с которыми придется сразиться Монокарпу.

В $$$j$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$D_j$$$ и $$$H_j$$$ ($$$1 \le D_j \le 10^6$$$; $$$1 \le H_j \le 10^{12}$$$).

Выходные данные

Выведите $$$m$$$ целых чисел. Для каждого монстра выведите минимальное количество монет, которое Монокарп должен потратить, чтобы убить этого монстра. Если это количество больше, чем $$$C$$$, то выведите $$$-1$$$.

Примеры
Входные данные
3 10
3 4 6
5 5 5
10 3 4
3
8 3
5 4
10 15
Выходные данные
5 3 -1
Входные данные
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
Выходные данные
14 4 14 4 7 7
Входные данные
5 13
13 1 9
6 4 5
12 18 4
9 13 2
5 4 5
2
16 3
6 2
Выходные данные
12 5
Примечание

Рассмотрим первого монстра из первого примера.

Монокарп не может взять одного воина первого типа, потому что и ему, и монстру потребуется $$$0.75$$$ секунды, чтобы убить друг друга. Он может взять двух воинов стоимостью $$$6$$$ монет и убить монстра за $$$0.375$$$ секунду.

Монокарп может взять одного воина второго типа, потому что он убивает монстра за $$$0.6$$$ секунды, а монстр убивает его за $$$0.625$$$ секунды. Воин быстрее. Таким образом, достаточно $$$5$$$ монет.

Монокарпу понадобится как минимум три воина третьего типа, чтобы убить первого монстра, что будет стоить $$$30$$$ монет.

Монокарп потратит меньше всего монет, если выберет второй тип воинов и возьмет одного воина этого типа.