Mr. Kim's Grocery Store (Small)
InterviewTime limit5sMemory limit512 MB
Given the sorted pile of 2N mixed normal and discounted price tags, recover the N sale prices.
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 . Then test cases follow. Each test case consists of two lines. The first line contains a single integer , the number of items in the store. The second line contains the integers that the printer produced in ascending order, separated by spaces.
- for every
- for every
- Every input has exactly one answer.
Output
For each test case, print one line in the format Case #x: y, where is the test case number starting from 1 and is the 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.