HSHW - Highschool Homework

Hugo had quite a bad day today. His favourite high school subject, mathematics, was taught by his least liked substitute teacher - he always gave out an abnormally large amount of homework. Today was no different.

The teacher wrote N numbers on the board, and after a long thoughtful pause he told the class with a grin: "Well then, kids. For today's homework you will do this harmless exercise. As you can see, I've written quite a few numbers on the board, and your task is to find which two of them have the greatest product. Hm, now that I think about it, that would be too trivial. So you will also have to find which pair of numbers has the greatest quotient. Well, and now that we're at it, why don't you find the pair with the smallest quotient, too. And at that point you might as well find the pair with the smallest product. That should keep you busy for today's evening!".

Sigh.

How could someone even come up with such a boring, time-consuming and impractical task. If only there was someone who would help Hugo and do it for him.

Input

The first line of input contains the number 1 ≤ T ≤ 15: the number of test cases. T cases follow. The first line of each case contains the number 2 ≤ N ≤ 105: how many numbers the teacher wrote on the board. The second line contains N integers; their absolute value will be in the range [1, 106] (inclusive). In particular, notice that none of them are equal to zero. You may assume that in any input file, the sum of N across all test cases does not exceed 3*105.

Output

For each case, output five lines. The first one contains the number of the case x in the format "Case x:", starting at 1.

Then output four lines, each containing two integers from the input (let's call them x and y). They need to have the following properties (in this order):

x * y is the greatest possible
x * y is the lowest possible
x / y is the greatest possible
x / y is the lowest possible

If there are multiple pairs of integers which fulfil the criteria, output the one with the lowest x. x, y may be equal, but in that case their value has to appear at least twice in the input. All four lines are independent, that is the same integer from the input may be used across multiple lines. A number A is said to be greater than B if A > B and lower than B if A < B.

Example

Input:
1
3
5 -7 10

Output:
Case 1:
5 10
-7 10
10 5
10 -7

Added by:Hodobox
Date:2017-04-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem

hide comments
2017-05-01 14:15:42
can you give me just one case that i'm falling on, i don't get it where have i done wrong

RE: looks like you have a small bug - in special cases you output x > y

--->I did it man but it was hard to find mistake in big code.
BTW Great problem man

Last edit: 2017-05-01 15:46:09
2017-04-30 23:06:44
for which cases is my program failing

RE: even for N=2!

Last edit: 2017-05-01 00:37:08
2017-04-26 15:37:20


Last edit: 2017-08-02 14:21:42
2017-04-20 20:54:07
Hey, can you check my solution? i even tested with brute, or did i miss something in the question.

RE: You have some cout << "0" in your code - why? Zeroes are never in the input, its in the input description. You have WA for some cases with N = 2.

---> Ya, considered 0's but if there are no 0's cout << "0" dont get executed , and i got wa bcaz of two spaces in between numbers at one point , got Accepted, thank you!

Last edit: 2017-04-21 04:25:52
2017-04-20 11:50:56
can you tell me where i am going wrong i am getting WA at 6th test case. I have checked my solution for all possible values but still getting it wrong.

RE: The first WA I found was an incorrect lowest x / y, N < 5

Last edit: 2017-04-20 12:04:58
2017-04-18 18:41:17 Vipul Srivastava
Am I still missing major test cases?

RE: You now only have WA on few cases N>1000

RE : I finally got it accepted. Thanks a lot for ur help. Was doing a very stupid mistake at last.
Very nice question. Thanks for it.

Last edit: 2017-04-20 14:08:16
2017-04-18 18:33:47 Vipul Srivastava
@ Hodobox can you guide me to where I am going wrong?

RE: The way you code your solution makes it easy to miss some cases, its difficult to give advice for it. Try to make a bruteforce solution and run both on a few random numbers - you have WA even for some cases where N = 2.

Last edit: 2017-04-18 18:38:34
2017-04-18 16:10:56 Vipul Srivastava
Ok thanks
2017-04-18 16:06:00 Vipul Srivastava
So there is no point of using 'quotient' or 'remainder'

RE: 'quotient' simply means the result of division, without any rounding in this problem

Last edit: 2017-04-18 16:08:09
2017-04-18 16:05:40 Vipul Srivastava
Ok so the quotient is decimal
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.