The Banzhaf Buzz-Off

Input

For each test case, the input will consist of two lines. The first line contains two integers $n$ and $q$ , where $n$ is the number of distinct weight values ( $1 \leq n \leq 60$ 1 \leq n \leq 60), and $q$ is the quota. The second line contains $n$ pairs of positive integers $w_{1} m_{1}, w_{2} m_{2}, \dots, w_{n} m_{n}$ w_1\ m_1,\ w_2\ m_2,\ \ldots,\ w_n\ m_n, where $w_{i}$ w_i is a weight value, and $m_{i}$ m_i is the number of board members with that weight. The total number of votes $V = w_{1} m_{1} + w_{2} m_{2} + \dots + w_{n} m_{n}$ V = w_1 m_1 + w_2 m_2 + \ldots + w_n m_n will be in the range $1 \leq V \leq 60$ 1 \leq V \leq 60. The quota satisfies the condition $V /2 < q \leq V$ V/2 < q \leq V, and all weights $w_{i}$ w_i are distinct, i.e., $w_{i} \neq = w_{j}$ w_i \ne w_j for $i \neq = j$ i \ne j. A line containing 0 0 signals the end of input.

Output

For each test case, output a single line in the form:

Case $n$ : $b_{1} b_{2} \dots b_{n}$ b_1\ b_2\ \ldots\ b_n

where $b_{i}$ b_i is the Banzhaf Power Index for any member with weight $w_{i}$ w_i. Separate the Banzhaf Power Indices with a single space.

Examples

Example 1

Loading