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? 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 1016, 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 22 BLANK 0 INVALID 4 A 65 B 35 43 BLANK 203 INVALID 287 Pragmatics 50 Paradigmatics 50 Programatics 50
2/2 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 A1 B1 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