Карафс — это овощ в форме прямоугольника размером 1 × h. Жители Тавасполиса любят карафс и кладут его почти в любую еду. Тавас просто без ума от карафса.

У каждого карафса положительная целочисленная высота. У Таваса есть бесконечная последовательность карафсов, пронумерованная с единицы. Высота i-го карафса равняется s_i = A + (i - 1) × B.

Зафиксируем целое положительное число m и определим операцию m-укуса как уменьшение высоты не более чем m различных несъеденных карафсов на 1. Карафс считается съеденным когда его высота становится равной нулю.

СаДДас дает Вам n запросов. В каждом запросе вам даются числа l, t и m и Вам надо найти наибольшее число r, такое, что l ≤ r и последовательность s_l, s_l + 1, ..., s_r можно съесть, произведя m-укус не более, чем t раз, либо выведите -1, если такого числа r не существует.