from bisect import bisect_left class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1) def sum(self, i): i += 1 s = 0 while i > 0: s += self.tree[i] i -= i & -i return s def sumrange(self, i, j): si = self.sum(i - 1) sj = self.sum(j) return sj - si def add(self, i, x): i += 1 while i <= self.size: self.tree[i] += x i += i & -i def lower_bound(self, w): if w <= 0: return 0 x = 0 r = 1 << (self.size).bit_length() while r > 0: if x+r < self.size and self.tree[x+r] < w: w -= self.tree[x+r] x += r r = r >> 1 return x class ConvexHullTrick_General(): def isneed(self, ismax, f1, f2, f3): va = (f3[1]-f2[1])*(f2[0]-f1[0]) vb = (f2[1]-f1[1])*(f3[0]-f2[0]) if ismax: return va < vb else: return va > vb def calc_value(self, x, line): a, b = line return a*x+b def __init__(self, lines_list, INF, ismax, isMonoq_get): self.ISMAX = ismax self.lines = [INF]+lines_list self.lines.sort(reverse=not self.ISMAX) self.state = Bit(len(self.lines)+2) self.state.add(0, 1) self.ct_all = 1 self.ISMONOQ = isMonoq_get def add_line(self, line): ind = bisect_left(self.lines, line) ct = self.state.sum(ind-1) if 0 < ct < self.ct_all: indl = self.state.lower_bound(ct) indr = self.state.lower_bound(ct+1) if not self.isneed(1, self.lines[indl], self.lines[ind], self.lines[indr]): return self.state.add(ind, 1) self.ct_all += 1 ct += 1 if ct == self.ct_all: indr0 = self.state.lower_bound(ct+1) while ct+1 < self.ct_all: indr1 = self.state.lower_bound(ct+2) if self.isneed(self.ISMAX, line, self.lines[indr0], self.lines[indr1]): break else: self.state.add(indr0, -1) ct -= 1 indr0 = indr1 if ct > 1: indl1 = self.state.lower_bound(ct-1) while ct > 2: indl0 = self.state.lower_bound(ct-2) if self.isneed(self.ISMAX, self.lines[indl0], self.lines[indl1], line): break else: self.state.add(indl1, -1) ct -= 1 self.ct_all -= 1 indl1 = indl0 def get_monoq(self, x): ind0 = self.state.lower_bound(1) res0 = self.calc_value(x, self.lines[ind0]) while self.ct_all > 1: ind1 = self.state.lower_bound(2) res1 = self.calc_value(x, self.lines[ind1]) if res0 < res1: self.state.add(ind0, -1) ind0 = ind1 res0 = res1 self.ct_all -= 1 else: break return res0 def get_general(self, x): l = 1 r = self.ct_all while r-l > 2: c = (r-l)//3 m0 = l+c m1 = r-c ind0 = self.state.lower_bound(m0) ind1 = self.state.lower_bound(m1) if (self.calc_value(x, self.lines[ind0]) < self.calc_value(x, self.lines[ind1])) ^ self.ISMAX: r = m1 else: l = m0 task = [self.calc_value(x, self.lines[self.state.lower_bound(i)]) for i in range(l, r+1)] if self.ISMAX: return max(task) else: return min(task) def get(self, x): if self.ISMONOQ: return self.get_monoq(x) else: return self.get_general(x) Ga = int(input()) Q = int(input()) query = [list(map(int, input().split())) for _ in range(Q)] lines = [] for q in query: if len(q) == 3: s, t = q[1:] lines.append([s+t, -s*t]) ans = [] cht = ConvexHullTrick_General(lines, [-1, -10**10], 1, 1) for q in query: if q[0] == 1: s, t = q[1:] cht.add_line([s+t, -s*t]) else: t = q[1] res = cht.get(t) ans.append(max(0, (-t**2+res)*Ga)) print(*ans, sep='\n')