Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Tavas and Karafs

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKarafs 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*.

Input

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.

Output

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

Examples

Input

2 1 4

1 5 3

3 3 10

7 10 2

6 4 8

Output

4

-1

8

-1

Input

1 5 2

1 5 10

2 7 4

Output

1

2

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2021 04:47:20 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|