3D Printing

You are a member of the executive committee for the Database Design Day festivities. You are in charge of promotions and want to print three D's to make a logo for the contest. You may print them in any color, but all three must be printed in the same color.

You have three printers, and you will use each one to print one of the D's. Every printer uses ink from four separate cartridges, one each for cyan, magenta, yellow, and black, to form a color. For these printers, a color is uniquely defined by four non-negative integers $c$, $m$, $y$, and $k$, which give the number of units of cyan, magenta, yellow, and black ink needed to make the color.

Printing one D requires exactly $10^6$ units of ink. For example, printing a D in pure yellow uses $10^6$ units of yellow ink and 0 units from every other cartridge. Printing a D in Code Jam red uses 0 units of cyan ink, 500000 units of magenta ink, 450000 units of yellow ink, and 50000 units of black ink.

To print a color, a printer must have at least the required amount of ink in each of its four color cartridges. Given the number of ink units each printer has in each cartridge, output any color, defined as four non-negative integers that sum to $10^6$, such that all three printers have enough ink to print it.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of three lines. The $i$-th line of a test case contains four integers $C_i$, $M_i$, $Y_i$, and $K_i$, the number of ink units in the $i$-th printer's cartridges for cyan, magenta, yellow, and black, respectively.

For each test case, output one line containing Case #x: r, where $x$ is the test case number starting from 1. If no color can be printed by all three printers, $r$ is IMPOSSIBLE. Otherwise, $r$ must be $c$ $m$ $y$ $k$, where $c$, $m$, $y$, and $k$ are non-negative integers that sum to $10^6$ and satisfy $c \le C_i$, $m \le M_i$, $y \le Y_i$, and $k \le K_i$ for all $i$. If there are multiple solutions, you may output any one of them.

Sample Case #1 is the image above. The proposed color uses all the ink in the first printer's cyan, magenta, and yellow cartridges and all the ink in the last printer's black cartridge. No additional unit could be used from any of the four ink colors, so the sample output is the only possible output for this case.

In Sample Case #2, magenta is the only color that both the first and second printers have, so the only chance is to use $10^6$ units of magenta. Unfortunately, the third printer does not have quite enough, so this case is impossible.

In Sample Case #3, other correct outputs include 400000 100000 100000 400000, 300000 0 0 700000, and 350000 140000 160000 350000, among many others. 300000 140000 160000 700000 would not be valid because, even though all printers have enough ink for it, the total number of ink units must be exactly $10^6$.