线性最大化

题目描述

在二维平面上有一个点集 $S$。初始时 $S$ 为空。

按顺序对每个 $i = 1, 2, \dots, Q$ 处理以下查询。

给定整数 $X_i$, $Y_i$, $A_i$ 和 $B_i$。先把点 $(X_i, Y_i)$ 加入 $S$,然后求出 $\displaystyle \max_{(x,y) \in S}\left\{A_ix + B_iy\right\}$。

输入格式

输入按以下格式从标准输入给出:

Q
X_1 Y_1 A_1 B_1
X_2 Y_2 A_2 B_2
⋮
X_Q Y_Q A_Q B_Q

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

样例

4
1 0 -1 -1
0 1 2 0
-1 0 1 1
0 -1 1 -2

-1
2
1
2

当 $i = 1$ 时:把点 $(1, 0)$ 加入 $S$,变为 $S = \{(1, 0)\}$。对于 $(x, y) = (1, 0)$,有 $-x - y = -1$,这是最大值。

当 $i = 2$ 时:把点 $(0, 1)$ 加入 $S$,变为 $S = \{(0, 1), (1, 0)\}$。对于 $(x, y) = (1, 0)$,有 $2x = 2$,这是最大值。

当 $i = 3$ 时:把点 $(-1, 0)$ 加入 $S$,变为 $S = \{(-1, 0), (0, 1), (1, 0)\}$。对于 $(x, y) = (1, 0)$ 或 $(x, y) = (0, 1)$,有 $x + y = 1$,这是最大值。

当 $i = 4$ 时:把点 $(0, -1)$ 加入 $S$,变为 $S = \{(-1, 0), (0, -1), (0, 1), (1, 0)\}$。对于 $(x, y) = (0, -1)$,有 $x - 2y = 2$,这是最大值。

9
-1 4 -8 -2
9 -9 -7 7
4 1 6 7
-4 -1 -4 -5
-9 3 -2 -6
-1 0 -8 5
-8 -5 0 0
8 3 0 -4
2 -5 2 5

0
35
31
21
36
87
0
36
31

数据范围

• 输入中的所有值均为整数。
• $1 \le Q \le 2 \times 10^5$
• $|X_i|, |Y_i|, |A_i|, |B_i| \le 10^9$
• 若 $i \neq j$,则 $(X_i, Y_i) \neq (X_j, Y_j)$。