The Banzhaf Buzz-Off

Each member of a board of trustees is assigned a number of votes (a weight) to use when the board votes on resolutions. A higher weight means more power, but exactly how much power a member has is subtle: it depends not only on how the weights are distributed but also on the quota, the number of votes needed to pass a resolution. For instance, with weights 20, 11, 10, 8, and 1, a member holding the single vote has almost no power under a simple-majority quota of 26, yet under a unanimity quota of 50 that member is exactly as powerful as everyone else.

This power is captured by the Banzhaf Power Index (BPI), which measures how often a member is a critical voter in a winning coalition. A winning coalition is a set of members whose total weight is greater than or equal to the quota (so they can pass a resolution). A member of a winning coalition is a critical voter if removing that member turns the coalition into a non-winning one. For example, with a quota of 26, the coalition consisting of the members with weights 20, 10, and 1 is winning; the members with weights 20 and 10 are each critical (removing either leaves only 11 or 21 votes), while the member with weight 1 is not critical. In the grand coalition of all five members, no one is critical when the quota is 26, but everyone is critical when the quota is 50.

The Banzhaf Power Index of a member is the total number of winning coalitions in which that member is critical. (The classical index is twice this count, but here we report the count itself.) Members with the same weight always have the same index. Since a board can have anywhere from 1 to 60 members and the weights may change over time, write a program that computes the index for each weight.

The input consists of several test cases. Each test case is given on two lines. The first line contains two integers n and q, where n is the number of distinct weight values (1 ≤ n ≤ 60) and q is the quota. The second line contains n pairs of positive integers w1 m1 w2 m2 ... wn mn, where wi is a weight value and mi is the number of board members having that weight. The total number of votes V = w1·m1 + w2·m2 + ... + wn·mn satisfies 1 ≤ V ≤ 60, the quota satisfies V/2 < q ≤ V, and the weights are distinct (wi ≠ wj when i ≠ j). A line containing 0 0 signals the end of the input.

For each test case, output a single line of the form Case k: b1 b2 ... bn, where k is the test-case number (starting at 1) and bi is the Banzhaf Power Index of any member whose weight is wi (in the same order as the input). Separate the indices with a single space.