SHOP

Interview

Time limit2sMemory limit512 MB

Summary

Given an amount to return and a limited supply of each bill denomination, choose bills of the highest denominations so the total equals the amount.

Level: Medium5 of 10
Topics: Greedy, Sorting, Implementation, Math
Solved: No attempts yet

Problem

Ahmad is a shopkeeper working in a market. When a customer pays him for shopping, he has to give back the change. Ahmad always wants to pay with the highest bills if possible. Write a program to help Ahmad.

Input

The first line contains $T$ , the number of test cases ( $0 < T < 100$ ).

Each test case has two lines. The first line contains the amount $M$ that Ahmad must return to the customer ( $1 \le M \le 1000000$ ). The second line contains $m_1:a_1, \dots, m_i:a_i, \dots, m_n:a_n$ . $m_i$ is the denomination of a bill and $a_i$ is the number of bills Ahmad has for that $m_i$ ( $1 \le m \le 1000000$ ).

Output

Print the bills Ahmad needs to return to the customer, sorted by denomination in descending order.

Examples1

Example 1

Input

3
235
5:10,10:6,20:4,50:3
370
10:4,5:20,40:4,70:3,100:2,50:5
172
10:4,5:20,40:4,70:3,100:2,50:5

Expected output

Customer1:
50 3
20 4
5 1
Customer2:
100 2
70 2
10 3
Customer3:
Impossible