Tavas and Karafs

题意翻译

问题描述 有无限个食品排成一排，其中第 i 个食品的体积 si 为 A + ( i - 1 ) * B 。 每一次，你最多可以同时吃 M 个食品，并使这 M 个食品的体积都减少 1 ，体积为 0 表示该食品被吃掉。 现在有 n 个询问，每个询问包含三个整数 L ， T ， M ，表示从第 L 个食品开始往右边吃，每次最多吃 M 个食品（ 可以是不连续的 M 个），最多吃 T 次，求一个最大的R ( L ≤ R ) ，使得第 L 个到第 R 个食品都被吃掉（必须是连续的）。 输入输出格式 输入格式 第一行，三个整数，A ， B ， n ( 1 ≤ A，B ≤ 10^6 ， 1 ≤ n ≤ 10^5 ) 接下来 n 行，每行表示一个询问，包含三个整数 L ， T ， M ( 1 ≤ L ， T ， M ≤ 10^6 ) 输出格式 输出共 n 行，每行一个整数，依次表示每个询问的 R ，无解则输出 −1 。 翻译由 @炼金法爷biu 提供

题目描述

Karafs is some kind of vegetable in shape of an $ 1×h $ rectangle. Tavaspolis people love Karafs and they use Karafs in almost any kind of food. Tavas, himself, is crazy about Karafs. Each Karafs has a positive integer height. Tavas has an infinite 1-based sequence of Karafses. The height of the $ i $ -th Karafs is $ s_{i}=A+(i-1)×B $ . For a given $ m $ , let's define an $ m $ -bite operation as decreasing the height of at most $ m $ distinct not eaten Karafses by 1. Karafs is considered as eaten when its height becomes zero. Now SaDDas asks you $ n $ queries. In each query he gives you numbers $ l $ , $ t $ and $ m $ and you should find the largest number $ r $ such that $ l<=r $ and sequence $ s_{l},s_{l+1},...,s_{r} $ can be eaten by performing $ m $ -bite no more than $ t $ times or print -1 if there is no such number $ r $ .

输入输出格式

输入格式

The first line of input contains three integers $ A $ , $ B $ and $ n $ ( $ 1<=A,B<=10^{6} $ , $ 1<=n<=10^{5} $ ). Next $ n $ lines contain information about queries. $ i $ -th line contains integers $ l,t,m $ ( $ 1<=l,t,m<=10^{6} $ ) for $ i $ -th query.

输出格式

For each query, print its answer in a single line.

输入输出样例

输入样例 #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