Under construction

Still being built. Things may change

Mr. Kim's Grocery Store (Small)

Interview

Time limit5sMemory limit512 MB

Summary
Given the sorted pile of 2N mixed normal and discounted price tags, recover the N sale prices.
Level

Medium5 of 10

Topics
Greedy, Hash map, Sorting
Solved
No attempts yet

Problem

Mr. Kim runs a grocery store in Incheon and is preparing a big sale. To keep the arithmetic simple he sells every item in the store at a 25% discount, so the sale price of each item is exactly 75% of its normal price. Every normal price in the store is an integer multiple of 4, so every sale price is an integer as well.

To get ready, Mr. Kim printed a discounted price tag for every item, and he also printed a normal price tag for every item so he can put the old prices back when the sale ends. While he was away serving a customer, the printer sorted all of the tags by price in ascending order and produced them as one single pile, with no separation between the two kinds. Both tags of every item are somewhere in that pile. The two kinds of tags look the same and Mr. Kim does not remember the price of every item, so he cannot tell which tags are the discounted ones. Work out the discounted prices from the pile alone.

For example, if the normal prices are 20, 80 and 100, the discounted prices are 15, 60 and 75, and the printed pile is 15, 20, 60, 75, 80, 100.

Input

The first line contains the number of test cases TT. Then TT test cases follow. Each test case consists of two lines. The first line contains a single integer NN, the number of items in the store. The second line contains the 2N2N integers P1,P2,…,P2NP_1, P_2, \dots, P_{2N} that the printer produced in ascending order, separated by spaces.

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤41 \le N \le 4
  • 1≤Pi≤1091 \le P_i \le 10^9 for every ii
  • Pi≤Pi+1P_i \le P_{i+1} for every ii
  • Every input has exactly one answer.

Output

For each test case, print one line in the format Case #x: y, where xx is the test case number starting from 1 and yy is the NN discounted prices in ascending order, separated by single spaces.

Hint

Several items can share the same price, and the discounted price of one item can equal the normal price of another item.

Examples2

  1. Example 1

    Input
    2
    3
    15 20 60 75 80 100
    4
    9 9 12 12 12 15 16 20
    
    Expected output
    Case #1: 15 60 75
    Case #2: 9 9 12 15
    
  2. Example 2

    Input
    1
    1
    3 4
    
    Expected output
    Case #1: 3