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: HARD
Tags: Sorting

Mathematics

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
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)))


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))


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)


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())))
	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)


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))


(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
	if l == ll:
		print(-1)
	else:
		print(r)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def possible(r):
	n = r - l + 1
	s = n * a + n * (n - 1) * B // 2
	return s <= m * t and a + B * (n - 1) <= t
(A, B, n) = value()
for _ in range(n):
	(l, t, m) = value()
	a = A + (l - 1) * B
	low = l
	high = 10 ** 10
	ans = -1
	while low <= high:
		mid = low + (high - low) // 2
		if possible(mid):
			ans = mid
			low = mid + 1
		else:
			high = mid - 1
	print(ans)


(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)


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)


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)


(a, b, n) = map(int, input().split())
for _ in range(n):
	(l, t, m) = map(int, input().split())
	lo = l
	hi = 100000000
	while lo < hi:
		mid = (lo + hi) // 2
		count = mid - l + 1
		first = a + (l - 1) * b
		last = a + (mid - 1) * b
		if last <= t and count * (first + last) // 2 <= m * t:
			lo = mid + 1
		else:
			hi = mid
	if mid != lo:
		print(mid)
	else:
		count = mid - 1 - l + 1
		first = a + (l - 1) * b
		last = a + (mid - 1 - 1) * b
		if last <= t and count * (first + last) // 2 <= m * t and (mid - 1 >= l):
			print(mid - 1)
		else:
			print(-1)


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)


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 sys
input = sys.stdin.readline
(a, b, n, l, t, m) = (-1, -1, -1, -1, -1, -1)

def is_valid(mid):
	biggest = a + (mid - 1) * b
	if t < biggest:
		return False
	sum = (mid - l + 1) * (a + (l - 1) * b + biggest) // 2
	return t >= biggest and m * t >= sum

def binary_search(b, e):
	while b <= e:
		mid = b + e >> 1
		if is_valid(mid):
			b = mid + 1
		else:
			e = mid - 1
	return b - 1
(a, b, n) = map(int, input().split())
for _ in range(n):
	(l, t, m) = map(int, input().split())
	res = binary_search(l, l + int(1000000.0))
	print(-1 if res == l - 1 else res)


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
	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
		sol = int((math.sqrt(D) - bb) / (2 * aa))
		sol = min(tth, sol)
		sol = l + sol - 1
		print(sol)
	n -= 1


from sys import stdin
(A, B, n) = [int(x) for x in stdin.readline().split()]
for q in range(n):
	(l, t, m) = [int(x) for x in stdin.readline().split()]
	l -= 1
	if B * l + A > t:
		print(-1)
	else:
		const = A * l + B * (l - 1) * l // 2
		high = (t - A) // B + 1
		low = l + 1
		while high >= low:
			mid = (low + high) // 2
			total = A * mid + B * mid * (mid - 1) // 2 - const
			if total <= t * m:
				low = mid + 1
			else:
				high = mid - 1
		print(high)