409586: GYM103640 B Because, Art!

Leo is a designer. He has a collection of $$$N$$$ fonts and $$$N$$$ colors, each of them having an integer grade that indicates how much beautiful it is. A negative grade indicates that the font or color is "ugly".

Based on that, Leo invented a new way of measuring the beauty of any text. If a text has a font of grade $$$F_i$$$ and a color of grade $$$C_j$$$, then the beauty of the text is the product $$$F_i \times C_j$$$. Note that when both the font and the color are ugly, the resulting text is beautiful, because, Art!

Leo has to present to his boss $$$k$$$ beautiful text designs. The boss said to him that the texts must be really different from each other. With this in mind, Leo decided to select a distinct font and a distinct color for each text in such a way that the sum of the beauties of the $$$k$$$ formed texts is maximum. For his pride, he also wants to know the minimum possible sum of the beauties of $$$k$$$ texts made of distinct fonts and colors.

But there is a problem! Leo forgot how many designs the boss asked for, so he needs to find the answer for each integer $$$k$$$ between $$$1$$$ and $$$N$$$.

The first line contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$) indicating the number of fonts and colors. The second line contains $$$N$$$ integers $$${F_1}, {F_2}, \ldots, {F_N}$$$ ($$$-10^4 \leq F_i \leq 10^4$$$ for $$${i}={1}, {2}, \ldots, {N}$$$), representing the grades of the fonts. The third line contains $$$N$$$ integers $$${C_1}, {C_2}, \ldots, {C_N}$$$ ($$$-10^4 \leq C_i \leq 10^4$$$ for $$${i}={1}, {2}, \ldots, {N}$$$), denoting the grades of the colors.

Output $$$N$$$ lines, such that the $$$k$$$-th line contains two integers indicating respectively the minimum and maximum sum of beauties if the boss asks for $$$k$$$ texts.

2
-100 -10
1 2

-200 -10
-210 -120

4
0 -1 1 2
10 20 30 40

-40 80
-40 110
-30 110
0 100