← 返回题目列表

Codeforces · 535/C

C. 塔瓦斯和卡拉夫

中文机器翻译题面 查看原题

Karafs 是一种形状为 1 × h 矩形的蔬菜。塔瓦斯波利斯人喜欢卡拉夫,他们几乎在任何食物中都使用卡拉夫。塔瓦斯本人对卡拉夫斯非常着迷。

每个 Karaf 都有一个正整数高度。 Tavas 有一个无限的基于 1 的 Karafses 序列。第 i 个 Karaf 的高度为 si = A + (i - 1) × B。

对于给定的 m,我们将 m 咬操作定义为将最多 m 个不同的未吃掉的 Karafs 的高度减少 1。当 Karafs 的高度变为零时,就认为它已被吃掉。

现在 SaDDas 向您询问 n 个问题。在每个查询中,他给你数字 l、t 和 m,你应该找到最大的数字 r,使得 l ≤ r 并且序列 sl, sl + 1, ..., sr 可以通过执行 m-bite 不超过 t 次来吃掉,或者如果没有这样的数字 r,则打印 -1。

输入

输入的第一行包含三个整数 A、B 和 n (1 ≤ A, B ≤ 106, 1 ≤ n ≤ 105)。

接下来的 n 行包含有关查询的信息。第 i 行包含第 i 个查询的整数 l、t、m (1 ≤ l, t, m ≤ 106)。

输出

对于每个查询,在一行中打印其答案。

示例

输入 #1

2 1 4
1 5 3
3 3 10
7 10 2
6 4 8

输出 #1

4
-1
8
-1

输入 #2

1 5 2
1 5 10
2 7 4

输出 #2

1
2