The Banzhaf Buzz-Off

이사회의 각 구성원에게는 안건 표결에 사용할 표의 수(가중치)가 배정되어 있다. 가중치가 클수록 힘이 세지만, 한 구성원이 실제로 얼마나 힘을 갖는지는 미묘한 문제다. 그것은 가중치의 분포뿐만 아니라, 안건을 통과시키는 데 필요한 표의 수인 정족수(quota)에도 달려 있다. 예를 들어 가중치가 20, 11, 10, 8, 1일 때, 단순 과반수 정족수 26에서는 1표를 가진 구성원의 힘이 거의 없지만, 만장일치 정족수 50에서는 그 구성원도 다른 모든 이와 똑같은 힘을 갖는다.

이 힘은 밴자프 파워 지수(Banzhaf Power Index, BPI)로 나타내며, 이는 한 구성원이 승리 연합에서 얼마나 자주 결정적 투표자가 되는지를 잰다. 승리 연합이란 가중치의 합이 정족수 이상인 구성원의 집합이다(즉 안건을 통과시킬 수 있다). 승리 연합의 어떤 구성원이 결정적 투표자라는 것은, 그 구성원이 빠지면 연합이 승리하지 못하게 된다는 뜻이다. 예를 들어 정족수가 26일 때, 가중치가 20, 10, 1인 구성원들로 이루어진 연합은 승리 연합이다. 여기서 가중치 20과 10인 구성원은 각각 결정적이지만(둘 중 하나가 빠지면 11표 또는 21표만 남는다), 가중치 1인 구성원은 결정적이지 않다. 다섯 명 모두로 이루어진 전체 연합에서는, 정족수가 26이면 아무도 결정적이지 않지만 정족수가 50이면 모두가 결정적이다.

한 구성원의 밴자프 파워 지수는 그 구성원이 결정적인 승리 연합의 총 개수이다. (고전적인 지수는 이 값의 두 배이지만, 여기서는 이 개수 자체를 보고한다.) 가중치가 같은 구성원들은 항상 같은 지수를 갖는다. 이사회의 구성원 수는 1명에서 60명까지 될 수 있고 가중치도 시간에 따라 바뀔 수 있으므로, 각 가중치에 대한 지수를 계산하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄로 주어진다. 첫째 줄에는 두 정수 n과 q가 있으며, n은 서로 다른 가중치 값의 개수(1 ≤ n ≤ 60), q는 정족수이다. 둘째 줄에는 n개의 양의 정수 쌍 w1 m1 w2 m2 ... wn mn이 주어지며, wi는 가중치 값이고 mi는 그 가중치를 가진 구성원의 수이다. 총 표 수 V = w1·m1 + w2·m2 + ... + wn·mn은 1 ≤ V ≤ 60을 만족하고, 정족수는 V/2 < q ≤ V를 만족하며, 가중치는 서로 다르다(i ≠ j이면 wi ≠ wj). 0 0만 있는 줄이 입력의 끝을 나타낸다.

각 테스트 케이스마다 Case k: b1 b2 ... bn 형식으로 한 줄을 출력한다. 여기서 k는 테스트 케이스 번호(1부터 시작)이고, bi는 가중치가 wi인 구성원의 밴자프 파워 지수이다(입력과 같은 순서). 지수들은 하나의 공백으로 구분한다.