24984번 - 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 × 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 ≤ N ≤ 10⁵) indicating the number of fonts and colors. The second line contains N integers F₁, F₂, . . . , F_N (−10⁴ ≤ F_i ≤ 10⁴ for i = 1, 2, . . . , N), representing the grades of the fonts. The third line contains N integers C₁, C₂, . . . , C_N (−10⁴ ≤ C_i ≤ 10⁴ for i = 1, 2, . . . , 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.