402947: GYM100957 B Опционы

Денис Борисов как-то решил попробовать свои силы на рынке опционов. Дело очень выгодное, ведь если получится что-нибудь заработать, то можно будет заработать еще больше на обучающих видео о том, как зарабатывать на опционах. Дело шло очень хорошо. Но чтобы оптимизировать процесс, Денису нужна программа, которая будет делать некоторые расчеты.

У Дениса есть список торговых площадок, на которых он может торговать опционами. На площадке номер i стоимость одного опциона составляет a_i рублей, а стоимость каждого дополнительного опциона составляет b_i рублей. Так, например, чтобы купить k опционов на площадке номер i, нужно заплатить a_i + (k - 1)·b_i рублей. Денису регулярно приходят письма от партнеров. Письмо с номером i содержит информацию о дополнительной торговой площадке (два целых числа a_i, b_i), а также запрос о том, за какую минимальную стоимость можно купить c_i опционов на одной из площадок, информация о которой известна на данный момент.

Дополнительно известно, что партнеры – люди серьезные и любят порядок. Поэтому информацию о площадках они решили присылать в порядке невозрастания чисел b_i. И все бы ничего, но программу сортировки они взяли с одного очень известного сайта, на котором автор сайта умышленно допустил ряд ошибок в алгоритме. Ошибки в алгоритме привели к тому, что числа b_i были отсортированы не совсем верно, а именно с точностью до пяти позиций. То есть для массива b_i выполнено соотношение b_i ≤ b_j, при i ≥ j + 5.

Помогите Денису справиться с поставленной задачей. Напишите программу, которая будет отвечать на письма партнеров.

В первой строке записано число 1 ≤ n ≤ 10⁵.

В следующих n строках записаны по три целых числа 1 ≤ a_i,  b_i,  c_i ≤ 10⁶.

Выведите n чисел, по одному в строке – ответы на каждое из писем от партнеров Дениса.

3
3 1 4
1 2 2
2 1 3

6
3
4