Leo 是一位设计师。他拥有一套 $N$ 种字体和 $N$ 种颜色，每种字体和颜色都有一个整数等级，表示其美观程度。负数等级表示该字体或颜色是“丑陋”的。

基于此，Leo 发明了一种衡量任何文本美观度的新方法。如果一段文本使用的字体等级为 $F_i$，颜色等级为 $C_j$，那么该文本的美观度就是乘积 $F_i \times C_j$。请注意，当字体和颜色都很“丑陋”时，最终的文本却是美丽的，因为这就是艺术！

Leo 需要向他的老板展示 $k$ 个精美的文本设计。老板告诉他，这些文本必须彼此完全不同。考虑到这一点，Leo 决定为每个文本选择一种不同的字体和一种不同的颜色，使得这 $k$ 个文本的美观度之和最大。为了他的自尊心，他还想知道由不同字体和颜色组成的 $k$ 个文本的美观度之和的最小值。

但现在有个问题！Leo 忘记了老板要求他设计多少个文本，所以他需要找出对于 $1$ 到 $N$ 之间的每个整数 $k$ 的答案。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示字体和颜色的数量。 第二行包含 $N$ 个整数 $F_1, F_2, \dots, F_N$ ($-10^4 \le F_i \le 10^4$，对于 $i = 1, 2, \dots, N$)，表示字体的等级。 第三行包含 $N$ 个整数 $C_1, C_2, \dots, C_N$ ($-10^4 \le C_i \le 10^4$，对于 $i = 1, 2, \dots, N$)，表示颜色的等级。

输出格式

输出 $N$ 行，其中第 $k$ 行包含两个整数，分别表示老板要求 $k$ 个文本时，美观度之和的最小值和最大值。

样例

样例输入 1

2
-100 -10
1 2

样例输出 1

-200 -10
-210 -120

样例输入 2

4
0 -1 1 2
10 20 30 40

样例输出 2

-40 80
-40 110
-30 110
0 100