题目描述

在二维平面上有一组点 $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\\}$。

约束条件

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

输入格式

输入以标准输入给出，格式如下：

$Q$ $X_1$ $Y_1$ $A_1$ $B_1$ $X_2$ $Y_2$ $A_2$ $B_2$ $\\vdots$ $X_Q$ $Y_Q$ $A_Q$ $B_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应该包含第 $i$ 个查询的答案。

示例输入 1

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

示例输出 1

-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$，这是最大值。

示例输入 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

示例输出 2

0
35
31
21
36
87
0
36
31