题目描述

$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\} $ を求める。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ 個目のクエリに対する答えを出力せよ。

题目大意

你有一个二元组集合 $S$ , 初始为空集.

有 $Q$ 次询问, 每次询问先把二元组 $(x_i,y_i)$ 加入集合 $S$ , 再回答 $\max\limits_{(x,y)\in S}\{a_ix+b_iy\}$ .

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

-1
2
1
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\ <\ =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)$

Sample Explanation 1

- $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$ となり、これが最大値を取ります。