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. [Image] 

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

Difficulty: interview

Starter code:

Solutions:
import sys
import math


a, b, n = list(map(int, str.split(sys.stdin.readline())))
s = lambda i: a + (i - 1) * b
S = lambda i: a * i + b * i * (i - 1) // 2
for _ in range(n):

    l, t, m = list(map(int, str.split(sys.stdin.readline())))
    # Si = a * r + b * r * (r - 1) / 2
    # Si = b / 2 * r ^ 2 - (b / 2 - a) * r
    # si = a + (i - 1) * b => (si - a) / b + 1 = i

    # (S(r) - S(l-1)) / t <= m
    # S(r) <= m * t + S(l-1)
    # b / 2 * r ^ 2 - (b / 2 - a) * r - m * t - S(l-1) <= 0
    # D = (b / 2 - a) ^ 2 + 4 * b / 2 * (m * t + S(l-1))
    d = (b / 2 - a) ** 2 + 4 * b / 2 * (m * t + S(l - 1))
    if d < 0:

        print(-1)
        continue

    r = min(
        math.floor((t - a) / b + 1),
        math.floor(((b / 2 - a) + math.sqrt(d)) / b)
    )
    if r < l:

        print(-1)

    else:

        print(r)


a,b,n=[int(x) for x in input().split()]
ltm=[[]]*n
for i in range(n):
    ltm[i]=[int(x) for x in input().split()]
for i in range(n):
    l,t,m=ltm[i]
    maxr=(t-a)//b+1
    minr=l
    while maxr>=minr:
        r=(maxr+minr)//2
        if t*m>=(r-l+1)*(2*a+b*(r+l-2))/2:
            minr=r+1
        else:
            maxr=r-1
    r=maxr
    if r<l:
        print(-1)
    else:
        print(r)

from math import sqrt

inp = input()

l = list(map(int, inp.split(' ')))
A = l[0]
B = l[1]
n = l[2]

for i in range(n):
    inp = input()
    temp = list(map(int, inp.split(' ')))
    l = temp[0]
    t = temp[1]
    m = temp[2]

    imp = 0
    a = B/2
    b = (A - 1/2 * B)
    c = -A * (l - 1) + 3*B*l/2 - B*l*l/2 - B - t*m

    res1 = 0

    if b*b - 4 * a * c > 0:
        res1 = int((-b + sqrt(b*b - 4 * a*c) )/ (2 *a))
    else:
        imp = 1

    res2 = 0

    if (t - A - B*(-1))/B > 0:
        res2 = int((t - A - B*(-1))/B)
    else:
        imp = 1
    if res2 < l:
        imp = 1

    if not imp:
        print(min(res1, res2))
    else:
        print(-1)


import math
A, B, n = map(int, input().split())
ans = []

for _ in range(n):
	l, t, m = map(int, input().split())
	
	if A + B * (l - 1) > t:
		ans.append(-1)
		continue

	r1 = (t - A) / B + 1
	D = (B-2*A)*(B-2*A)-4*B*(-2*l*A+2*A-B*(l-2)*(l-1)-2*m*t)
	r2 = int(((B-2*A) + math.sqrt(D)) / 2 / B)

	if r1 > r2:
		r1 = r2
	ans.append(int(r1))


print("\n".join(map(str, ans)))

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 15 01:59:52 2015

codeforces 299 Div 2 C
"""
import sys


def read_data():
    A, B, n = list(map(int, input().split()))
    ltm = sys.stdin.readlines()
    return A, B, ltm


def solve(A, B, ltm):
    for line in ltm:
        L, t, m = list(map(int, line.split()))
        print(max_r(L, t, m, A, B))

memo = dict()
def max_r(L, t, m, A, B):
    nonlocal memo
    if (L, t, m) in memo:
        return memo[L, t, m]
    r_upper = (t - A) // B + 2
    if r_upper <= L:
        memo[L, t, m] = -1
        return -1
    r_lower = L
    threshold = t * m
    while r_upper > r_lower + 1:
        mid = (r_upper + r_lower) // 2
        if (2 * A + B * (L + mid - 2)) * (mid - L + 1) // 2 <= threshold:
            r_lower = mid
        else:
            r_upper = mid
    memo[L, t, m] = r_lower
    return r_lower


A, B, ltm = read_data()
solve(A, B, ltm)


import math
s=input()
a,b,n=s.split()
a,b,n=int(a),int(b),int(n)
for cas in range(0,n):
    s=input()
    l,t,m=s.split()
    l,t,m=int(l),int(t),int(m)
    L,R=l,(t-a)//b+1
    if R<L:
        print(-1)
        continue
    else:
        A=b
        B=2*a-b
        C=(2*a+b*l-2*b)*(1-l)-2*t*m
        ans=(-B+math.sqrt(B*B-4*A*C))/2/A
        if ans>R:
            ans=R
        print(int(ans))
        


import math
a, b, n = [int(x) for x in input().split()]

for i in range(n):
    l, t, m = [int(x) for x in input().split()]
    x = a + (l - 1) * b
    if x > t:
        print("-1")
        continue

    r = (t - a) // b + 1
    D = (2 * x - b) ** 2 + 8 * m * t * b
    d = int(math.floor((-2 * x + b + math.sqrt(D)) / (2 * b)))
    r = min(r, l + d - 1)
    # total = t * m
    # last = a + (r - 1) * b
    # total_need = (x + last) * (r - l + 1) // 2
    # while total_need > total:
    #     total_need -= last
    #     last -= b
    #     r -= 1
    print(r)


import math

a, b, n = [int(x) for x in input().split()]
for i in range(n):
    l, t, m = [int(x) for x in input().split()]
    x = a + (l - 1) * b
    if x > t:
        print("-1")
        continue
    r = (t - a) // b + 1
    D = (2 * x - b) ** 2 + 8 * m * t * b
    d = int(math.floor((-2 * x + b + math.sqrt(D)) / (2 * b)))
    r = min(r, l + d - 1)
    print(r)

import math

A, B, n = map(int, input().split())
lCurKarafs = 0; lSum = 0; aa = 0; bb = 0; c = 0; D = 0; sol = 0; tth = 0;
while(n > 0):
    l, t, m = map(int, input().split())
    lCurKarafs = A + (l - 1) * B;
    #print(str(lCurKarafs) + " " + str(t) + " " + str(m))
    lSum = m * t;
    if(lCurKarafs > t):
        print(-1)
    elif(lCurKarafs == t):
        print(l)
    else:
        tth = (t - lCurKarafs + B) // B;
        aa = B; bb = 2 * lCurKarafs - B; c = (-2) * lSum;
        D = bb * bb - 4 * aa * c;
        #D = math.sqrt(D);
        sol = int((math.sqrt(D) - bb) / (2 * aa));
        sol = min(tth, sol);
        sol = l + sol - 1;
        print(sol)
    n -= 1

import math

A, B, n = map(int, input().split())
lCurKarafs = 0; lSum = 0; aa = 0; bb = 0; c = 0; D = 0; sol = 0; tth = 0;
while(n > 0):
    l, t, m = map(int, input().split())
    lCurKarafs = A + (l - 1) * B;
    #print(str(lCurKarafs) + " " + str(t) + " " + str(m))
    lSum = m * t;
    if(lCurKarafs > t):
        print(-1)
    elif(lCurKarafs == t):
        print(l)
    else:
        tth = (t - lCurKarafs + B) // B;
        aa = B; bb = 2 * lCurKarafs - B; c = (-2) * lSum;
        D = bb * bb - 4 * aa * c;
        #D = math.sqrt(D);
        sol = int((math.sqrt(D) - bb) / (2 * aa));
        sol = min(tth, sol);
        sol = l + sol - 1;
        print(sol)
    n -= 1

f = lambda: map(int, input().split())
A, B, n = f()
for i in range(n):
    l, t, m = f()
    S = 2 * (A + B * l) - B
    T = S - B - 2 * m * t
    r = l + int(((S * S - 4 * B * T) ** 0.5 - S) / (2 * B))
    r = min(r, (t - A) // B + 1)
    print(-1 if r < l else r)

f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)


f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)



f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)



f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)



f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)



f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)



f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)



f = lambda: list(map(int, input().split()))
A, B, n = f()
k = 0.5
for i in range(n):
    l, t, m = f()
    b = A / B + l - k
    c = b - k - (m * t) / B
    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)
    print(-1 if r < l else r)



f = lambda: list(map(int, input().split()))

A, B, n = f()

k = 0.5

for i in range(n):

    l, t, m = f()

    b = A / B + l - k

    c = b - k - (m * t) / B

    r = min(l + int((b * b - 2 * c) ** k - b), (t - A) // B + 1)

    print(-1 if r < l else r)






# Made By Mostafa_Khaled


R = lambda: map(int, input().split())
a, b, n = R()
for _ in range(n):
    l, t, m = R()
    ll, rr = l - 1, 10**6 + 7
    sl = a + (l - 1) * b
    while ll < rr:
        mm = (ll + rr + 1) // 2
        sr = a + (mm - 1) * b
        slr = (sl + sr) * (mm - l + 1) // 2
        if slr <= t * m and sr <= t:
            ll = mm
        else:
            rr = mm - 1
    if ll >= l:
        print(ll)
    else:
        print(-1)

import math
a,b,n =[int(x) for x in input().split()]
for i in range(n):
    l,t,m=[int(x) for x in input().split()]
    x=a+(l-1)*b
    if x>t:
        print("-1")
        continue
    r=(t-a)//b+1
    D=(2*x-b)**2+8*m*t*b
    d=int(math.floor((-2*x+b+math.sqrt(D))/(2*b)))
    print(min(r,l+d-1))





'''
////////////////      //////        ///////      //             ///////     //  //   //
////          //    ///   ///     ///    ///     //            ///  ///     ////     //
////    ////       ///     ///   ///      ///    //           /////////     ////     ///////
////     /////    ///       /// ///        ///   //          ///    ///     ////     //   //
//////////////     ///////////   ///////////     //////     ///     ///     //  //   //   //
'''



a,b,n = list(map(int,input().split()))
lis=[0]+[(a+ i*b) for i in range(1000001)]
for i in range(n):
    ll,t,m = list(map(int,input().split()))
    l=ll
    r=(t-a)//b+1
    while l<=r:
        mid = l+(r-l)//2
        ter = mid-ll+1
        su = ((ter)*(2*lis[ll] + (ter-1)*b))//2
        if t*m>=su and lis[mid]<=t:
            l=mid+1
        else:
            r=mid-1
#    print(l,r)        
    if l==ll:
        print(-1)
    else:
        print(l-1)              



a,b,n = list(map(int,input().split()))
lis=[0]+[(a+ i*b) for i in range(1000001)]
for i in range(n):
    ll,t,m = list(map(int,input().split()))
    l=ll
    r=(t-a)//b+1
    while l<=r:
        mid = l+(r-l)//2
        ter = mid-ll+1
        su = ((ter)*(2*lis[ll] + (ter-1)*b))//2
        if t*m>=su and lis[mid]<=t:
            l=mid+1
        else:
            r=mid-1
#    print(l,r)        
    if l==ll:
        print(-1)
    else:
        print(r)                         



a,b,n = map(int,input().split())
lis=[0]+[(a+ i*b) for i in range(1000001)]
for i in range(n):
    ll,t,m = map(int,input().split())
    l=ll
    r=(t-a)//b+1
    while l<=r:
        mid = l+(r-l)//2
        ter = mid-ll+1
        su = ((ter)*(2*lis[ll] + (ter-1)*b))//2
        if t*m>=su and lis[mid]<=t:
            l=mid+1
        else:
            r=mid-1
#    print(l,r)        
    if l==ll:
        print(-1)
    else:
        print(r)