The Banzhaf Buzz-Off
A young researcher named George Lurdan has just been promoted to the board of trustees for Amalgamated Artichokes. Each member of the board has a speci ed number of votes (or weights) assigned to him or her which can be used when voting on various issues that come before the board. Needless to say, the higher your weight, the more power you have on the board, but exactly how much power you have is a dicult question. It depends not only on the distribution of the weights, but also on what percentage of the votes are needed to pass any resolution (known as the quota). For example, the current board has 5 members whose weights are 20, 11, 10, 8 and 1, where George has the 1. Whenever a simple majority of votes are needed (i.e., when the quota is 26) George has very little power. But when the vote has to be unanimous (quota = 50), George has just as much power as anyone else. George would like to know how much power he has depending on what the quota is; he gures that if his power is zero, then there's no point in going to the meetings|he can buzz o and spend more time on artichoke research.
After doing some reading, George discovered the Banzhaf Power Index (BPI). The BPI measures how often each board member is a critical voter in a winning coalition. A winning coalition is a group of board members whose total weights are greater than or equal to the quota (i.e., they can pass a resolution). A critical voter in a winning coalition is any member whose departure results in a nonwinning coalition. For example, if the quota is 26, then one possible winning coalition would consist of 20, 10 and 1 (George). Here, each of the rst two members of the coalition are critical (since if they leave the resulting coalition has only 11 or 21 votes), while George is not critical. In the winning coalition 20, 11, 10, 8, 1, no one is critical when the quota is 26, but everyone is when the quota is 50. The BPI for any member is just the total number of winning coalitions in which that member is critical (NOTE: in reality, the BPI is actually double this gure, but that's not important for us here). For example, when the quota is 26, the BPIs for the members turn out to be 12, 4, 4, 4 and 0, i.e., the board member with weight 20 is a critical voter in 12 di erent winning coalitions, the board member with weight 11 is a critical voter in 4 di erent winning coalitions, etc. As expected, George has no power in this case. If the quota is raised to 42, then the BPIs are 3, 3, 3, 1 and 1. In this case George has just as much power as the member with 8 votes!
Since the number of members on the board can vary from 1 to 60 , and board members' weights can change over time, George would like a general program to determine his BPI power.
Input
Input for each test case will consist of two lines: the first line will contain two integers n, q, where n indicates the number of distinct weight values (1 ≤ n ≤ 60) and q is the quota. The second line will contain n pairs of positive integers w_1 m_1 w_2 m_2 ... w_n m_n where w_i is a weight value and m_i is the number of board members with that weight. The total number of votes V = w_1m_1+w_2m_2+...+w_nm_n will be in the range 1 ≤ V ≤ 60. The quota will satisfy the condition V/2 < q ≤ V, and w_i ≠ w_j when i ≠ j. A line containing "0 0" will signal the end of input.
Output
For each test case, output a single line of the form:
Case n: b_1 b_2 ... b_n
where b_i is the Banzhaf Power Index for any member with weight w_i. Separate the BPIs with a single blank.