Карафс — это овощ в форме прямоугольника размером 1 × h. Жители Тавасполиса любят карафс и кладут его почти в любую еду. Тавас просто без ума от карафса.
У каждого карафса положительная целочисленная высота. У Таваса есть бесконечная последовательность карафсов, пронумерованная с единицы. Высота i-го карафса равняется si = A + (i - 1) × B.
Зафиксируем целое положительное число m и определим операцию m-укуса как уменьшение высоты не более чем m различных несъеденных карафсов на 1. Карафс считается съеденным когда его высота становится равной нулю.
СаДДас дает Вам n запросов. В каждом запросе вам даются числа l, t и m и Вам надо найти наибольшее число r, такое, что l ≤ r и последовательность sl, sl + 1, ..., sr можно съесть, произведя m-укус не более, чем t раз, либо выведите -1, если такого числа r не существует.