Problem Statement

There is a set S of points on a two-dimensional plane. S is initially empty.
For each $i = 1, 2, \dots, Q$ in this order, process the following query.

• You are given integers X_i, Y_i, A_i, and B_i. Add point (X_i, Y_i) to S, and then find $\displaystyle \max_{(x,y) \in$ $S}\left$${A_ix + B_iy\right$}.

Input

Input is given from Standard Input in the following format:
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

Output

Print Q lines. The i-th line should contain the answer for the i-th query.

Constraints

• All values in input are integers.
• 1≤Q≤$2 \times 10^5$
• |X_i|, |Y_i|, |A_i|, |B_i| ≤10^9
• If i ≠ j, then (X_i, Y_i) ≠ (X_j, Y_j).

Sample Input 1

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

Sample Output 1

-1
2
1
2

• When i = 1: add point (1, 0) to S, then it will become S = {(1, 0)}. For (x, y) = (1, 0), we have -x - y = -1, which is the maximum.
• When i = 2: add point (0, 1) to S, then it will become S = {(0, 1), (1, 0)}. For (x, y) = (1, 0), we have 2x = 2, which is the maximum.
• When i = 3: add point (-1, 0) to S, then it will become S = {(-1, 0), (0, 1), (1, 0)}. For (x, y) = (1, 0) or (x, y) = (0, 1), we have x + y = 1, which is the maximum.
• When i = 4: add point (0, -1) to S, then it will become S = {(-1, 0), (0, -1), (0, 1), (1, 0)}. For (x, y) = (0, -1), we have x - 2y = 2, which is the maximum.

Sample Input 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

Sample Output 2

0
35
31
21
36
87
0
36
31

见题面 Input 部分

见题面 Output 部分