题目描述

すぬけ君は長さ $N$ の数列 $a,b$ を持っています。 $a,b$ の $i$ 番目の数はそれぞれ $a_i,b_i$ です。

すぬけ君は $a,b$ を使って長さ $N$ の数列 $c$ を作ることにしました。 $1\ \leq\ n\ \leq\ N$ を満たす $n$ について、$c$ の $n$ 番目の数 $c_n$ は $1\ \leq\ i\ \leq\ j\ \leq\ n$ を満たすような $(i,j)$ について $a_i\ b_j$ を計算したときの最大値です。より形式的には $c_n$ は $ c_n\ =\ \max_{1\ \leq\ i\ \leq\ j\ \leq\ n}\ a_{i}b_{j} $ で表される数です。

$c_1,\ c_2,\ \ldots,\ c_{N}$ を求めてください。

输入格式

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

$N$ $a_{1}$ $a_{2}$ $\cdots$ $a_{N}$ $b_{1}$ $b_{2}$ $\cdots$ $b_{N}$

输出格式

$N$ 行出力せよ。上から $n$ 行目では $c_{n}$ を出力せよ。

题目大意

你有一个长 $N$ 的数列 $a,b$ ，数列 $a$ 第 $i$ 个数是 $a_i$ ，数列 $b$ 的第 $j$ 个数是 $b_j$ 。
你想用数列 $a,b$ 来制作长度N的数列 $c$。对于满足 $1≤n≤N$ 的 $n,c$ 的第 $n$ 个数 $c_n$ 对于满足 $\big(i,j\big)$ $(1≤i≤j≤n)$ 的 $a_i\times b_j$ 计算 $j$ 时的最大值。更具体地，$c_n$是 $c_n\max_{1≤i≤j≤n}a_i\times b_j$表示。
$c_1,c_2,\cdots,c_N$ 求值时使用曲面法线的原始方向。
输入以以下形式给出：

$N$
$a_1,a_2,\cdots,a_n$
$b_1,b_2,\cdots,b_n$

执行 $N$ 次操作，在各操作中执行以下步骤。

在第 $n$ 次操作中，对于满足 $1≤i≤n$ 的所有 $i$，$a_i\times b_n$，并将其最大值设为 $c_n$。

各操作的计算量为 $\mathrm{O(n)}$，但由于进行 $N$ 次操作，因此合计需要$\mathrm{O(N^2)}$的计算量。

友情提示：岛国题必须要换行，否则你就等着红紫世界吧！

3
3 2 20
1 4 1

3
12
20

20
715806713 926832846 890153850 433619693 890169631 501757984 778692206 816865414 50442173 522507343 546693304 851035714 299040991 474850872 133255173 905287070 763360978 327459319 193289538 140803416
974365976 488724815 821047998 371238977 256373343 218153590 546189624 322430037 131351929 768434809 253508808 935670831 251537597 834352123 337485668 272645651 61421502 439773410 621070911 578006919

697457706539596888
697457706539596888
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026

提示

制約

• 与えられる入力は全て整数
• $1\ \leq\ N\ \leq\ 2\ \times\ 10^{5}$
• $1\ \leq\ a_i,\ b_i\ \leq\ 10^9$

Sample Explanation 1

- $c_{1}\ =\ \max(a_{1}b_{1})\ =\ 3$ です。 - $ c_{2}\ =\ \max(a_{1}b_{1},\ a_{1}b_{2},a_{2}b_{2})\ =\ 12 $ です。 - $ c_{3}\ =\ \max(a_{1}b_{1},\ a_{1}b_{2},\ a_{1}b_{3},\ a_{2}b_{2},a_{2}b_{3},a_{3}b_{3})\ =\ 20 $ です。