3D 프린팅

당신은 Database Design Day 행사의 운영위원회 일원이다. 홍보를 맡고 있으며, 대회 로고로 쓸 D 세 개를 인쇄하려 한다. 세 D는 원하는 색으로 인쇄할 수 있지만 모두 같은 색이어야 한다.

프린터 세 대가 주어지고, 각 프린터로 D 하나씩을 인쇄한다. 모든 프린터는 시안, 마젠타, 옐로, 블랙의 서로 다른 색 잉크 카트리지 네 개에 든 잉크로 색을 만든다. 이 프린터에서 색은 그 색을 만드는 데 필요한 시안, 마젠타, 옐로, 블랙 잉크의 단위 수를 나타내는 음이 아닌 정수 $c$, $m$, $y$, $k$ 네 개로 유일하게 정의된다.

D 하나를 인쇄하는 데 필요한 잉크의 총량은 정확히 $10^6$ 단위이다. 예를 들어 D를 순수한 노란색으로 인쇄하면 노란 잉크 $10^6$ 단위를 쓰고 다른 잉크는 0 단위를 쓴다. D를 Code Jam 빨간색으로 인쇄하면 시안 잉크 0 단위, 마젠타 잉크 500000 단위, 옐로 잉크 450000 단위, 블랙 잉크 50000 단위를 쓴다.

어떤 색을 인쇄하려면 프린터의 색 카트리지 네 개 각각에 그 색에 필요한 양 이상의 잉크가 있어야 한다. 각 프린터의 각 카트리지에 든 잉크 단위 수가 주어질 때, 세 프린터 모두 그 색을 인쇄할 만큼 충분한 잉크를 가진 색을 하나 출력하라. 색은 합이 $10^6$인 음이 아닌 정수 네 개로 정의한다.

입력의 첫 줄에는 테스트 케이스 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 테스트 케이스의 $i$번째 줄에는 $i$번째 프린터의 시안, 마젠타, 옐로, 블랙 카트리지에 든 잉크 단위 수를 나타내는 정수 $C_i$, $M_i$, $Y_i$, $K_i$가 주어진다.

각 테스트 케이스에 대해 Case #x: r 형식의 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이다. 세 프린터 모두 인쇄할 수 있는 색이 없으면 $r$은 IMPOSSIBLE이다. 그렇지 않으면 $r$은 $c$ $m$ $y$ $k$여야 한다. 여기서 $c$, $m$, $y$, $k$는 합이 $10^6$인 음이 아닌 정수이고, 모든 $i$에 대해 $c \le C_i$, $m \le M_i$, $y \le Y_i$, $k \le K_i$를 만족한다. 정답이 여러 개면 그중 아무거나 출력해도 된다.

예제 케이스 #1은 위에 제시된 그림이다. 제안된 색은 첫 번째 프린터의 시안, 마젠타, 옐로 카트리지에 든 잉크를 모두 사용하고 마지막 프린터의 블랙 카트리지에 든 잉크를 모두 사용한다. 따라서 잉크 색 네 가지 중 어느 것에서도 잉크를 한 단위 더 쓸 수 없으므로, 주어진 예제 출력은 이 케이스의 유일한 가능한 출력이다.

예제 케이스 #2에서 마젠타는 첫 번째와 두 번째 프린터가 모두 가진 유일한 색이므로, 유일한 가능성은 마젠타 $10^6$ 단위를 쓰는 것이다. 아쉽게도 세 번째 프린터에는 그만큼의 마젠타 잉크가 없어서 이 케이스는 불가능하다.

예제 케이스 #3에서 다른 정답으로는 400000 100000 100000 400000, 300000 0 0 700000, 350000 140000 160000 350000 등이 많이 있다. 300000 140000 160000 700000은 모든 프린터에 그 양을 인쇄할 잉크가 충분하더라도 잉크 단위 수의 합이 정확히 $10^6$이어야 하므로 유효한 정답이 아니다.