問題文

$2$ 次元平面上の点の集合 $S$ があります。$S$ ははじめ空です。

$i = 1, 2, \\dots, Q$ の順に、以下のクエリを処理してください。

• 整数 $X_i, Y_i, A_i, B_i$ が与えられる。$S$ に点 $(X_i, Y_i)$ を追加した後、$\\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$ のとき : $S$ に点 $(1, 0)$ を追加し、$S = \\{(1, 0)\\}$ とします。$(x, y) = (1, 0)$ のとき $\-x - y = -1$ となり、これが最大値を取ります。
• $i = 2$ のとき : $S$ に点 $(0, 1)$ を追加し、$S = \\{(0, 1), (1, 0)\\}$ とします。$(x, y) = (1, 0)$ のとき $2x = 2$ となり、これが最大値を取ります。
• $i = 3$ のとき : $S$ に点 $(-1, 0)$ を追加し、$S = \\{(-1, 0), (0, 1), (1, 0)\\}$ とします。$(x, y) = (1, 0)$ または $(x, y) = (0, 1)$ のとき $x + y = 1$ となり、これが最大値を取ります。
• $i = 4$ のとき : $S$ に点 $(0, -1)$ を追加し、$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