Background

After solving the easy problem of municipal elections... we want more! More parties! More voters! More councilors!

Would you be able to deal with hundreds of parties, billions of councilors, trillions of voters?

The Problem

Given the number of councilors that have to be elected, the number of votes for each party, and the number of blank and invalid votes, you have to compute the number of councilors assigned to each party.

As in the previous problem, you have to observe the rule of proportionality: the number of assigned councilors has to be proportional (the maximum possible) to the number of obtained votes. In other words, there exists a number of votes, X, such that when a party has X votes, then they win a councilor. If two or more parties have exactly the same proportion to obtain a councilor, then you have to assign it to the first party in alphabetical order.

Input

The input can contain different test cases. The first line of the input indicates the number of test cases.

For each test case, the first line contains 2 natural numbers: N, P. Number N indicates the number of councilors to be elected, while P indicates the number of existing political parties.

The following two lines contain the text:

BLANK B
INVALID I

Where B and I indicate the number of blank and invalid votes, respectively. Next, there are P lines, one for each party. Each line contains two values: a string without blank spaces, indicating the name of the party; and a number, indicating the number of votes for that party.

You can assume that N and the number of votes are always between 0 and 10¹⁶, inclusive.

Output

For each test case, you have to output the councilors obtained for each party, in the same order as they appear in the input. Thus, you have to output P lines, with the name of the party and the number of councilors assigned to that party, separated by a blank space.

Sample Input

4
2 2
BLANK 0
INVALID 4
A 65
B 35
4 3
BLANK 203
INVALID 287
Pragmatics 50
Paradigmatics 50
Programatics 50
360000000000 5
BLANK 0
INVALID 92
One 26572000000000
Two 28863000000000
Three 6231000000000
Four 832000000000
Five 0
360 5
BLANK 0
INVALID 92
One 26572000000000
Two 28863000000000
Three 6231000000000
Four 832000000000
Five 0

Sample Output

A 1
B 1
Pragmatics 1
Paradigmatics 2
Programatics 1
One 153059617908
Two 166256200199
Three 35891708534
Four 4792473359
Five 0
One 153
Two 167
Three 36
Four 4
Five 0

OMP'11
Facultad de Informatica
Universidad de Murcia (SPAIN)