25089번 - 3D Printing 서브태스크스페셜 저지다국어

문제

You are part of the executive committee of the Database Design Day festivities. You are in charge of promotions and want to print three D's to create a logo of the contest. You can choose any color you want to print them, but all three have to be printed in the same color.

You were given three printers and will use each one to print one of the D's. All printers use ink from 4ドル$ individual cartridges of different colors (cyan, magenta, yellow, and black) to form any color. For these printers, a color is uniquely defined by 4ドル$ non-negative integers $c,ドル $m,ドル $y,ドル and $k,ドル which indicate the number of ink units of cyan, magenta, yellow, and black ink (respectively) needed to make the color.

The total amount of ink needed to print a single D is exactly 10ドル^6$ units. For example, printing a D in pure yellow would use 10ドル^6$ units of yellow ink and 0ドル$ from all others. Printing a D in the 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 for each of its 4ドル$ color cartridges. Given the number of units of ink each printer has in each cartridge, output any color, defined as 4ドル$ non-negative integers that add up 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 3ドル$ lines. The $i$-th line of a test case contains 4ドル$ integers $C_i,ドル $M_i,ドル $Y_i,ドル and $K_i,ドル representing the number of ink units in the $i$-th printer's cartridge for the colors 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) and $r$ is IMPOSSIBLE if there is no color that can be printed by all 3ドル$ printers. Otherwise, $r$ must be equal to "$c$ $m$ $y$ $k$" where $c,ドル $m,ドル $y,ドル and $k$ are non-negative integers that add up to 10ドル^6$ and $c≤C_i,ドル $m≤M_i,ドル $y≤Y_i,ドル and $k≤K_i,ドル for all $i$.

If there are multiple solutions, you may output any one of them.

제한

서브태스크 1 (13점)

• 1ドル≤T≤100$.
• 0ドル≤C_i≤10^6,ドル for all $i$.
• 0ドル≤M_i≤10^6,ドル for all $i$.
• 0ドル≤Y_i≤10^6,ドル for all $i$.
• 0ドル≤K_i≤10^6,ドル for all $i$.

힌트

Sample Case #1 is the image provided above. The proposed color is using up all of the ink in the cyan, magenta, and yellow cartridges of the first printer and all of the ink in the black cartridge of the last printer. This means that no additional unit of ink could be used from any of the 4ドル$ ink colors, so the given 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 our only chance would be to use 10ドル^6$ units of magenta. Unfortunately, the third printer does not have quite enough, making this case impossible.

In Sample Case #3, other correct outputs are: "400000 100000 100000 400000", "300000 0 0 700000", and "350000 140000 160000 350000", among lots of others. Notice that "300000 140000 160000 700000" would not be a valid answer because, even though there is enough ink in all printers to do that, the total number of ink units must be exactly 10ドル^6$.