7. Daj het

Máme štvorcovú tabuľku. V tabuľke máme prirodzené čísla. Pekne spôsobne, v každom políčku jedno.

Každý riadok aj každý stĺpec má pri sebe napísané jedno číslo. Toto číslo hovorí, aký súčet chceme v danom riadku/stĺpci dosiahnuť.

Úloha

Daj het niektoré čísla z tabuľky tak, aby všetky súčty sedeli.

Formát vstupu

Toto je open data úloha, dostanete teda od nás úplne všetky vstupy. Môžete sa na ne ľubovoľne pozerať a robiť s nimi čo len chcete. Vstupov je 8 a volajú sa 1.in až 8.in. Každý vstup začína číslom \(t\) predstavujúcim počet testov, ktoré obsahuje. Každý test má nasledujúci formát:

• V prvom riadku je číslo \(n\): rozmer tabuľky. (V každom vstupe majú všetky testy rovnaké \(n\).)
• V druhom riadku je \(n\) čísel: predpísané súčty pre riadky zhora dole.
• V treťom riadku je \(n\) čísel: predpísané súčty pre stĺpce zľava doprava.
• V každom z nasledujúcich \(n\) riadkov je \(n\) kladných celých čísel nepresahujúcich \(20\), v poradí, v akom sú rozmiestnené v tabuľke.

Môžete predpokladať, že pre každú zo zadaných tabuliek existuje aspoň jedno riešenie.

Vstupy pre windows tu, pre linux tu.

Formát výstupu

Odovzdajte zip archív a v ňom príslušné výstupy. Tie musia byť pomenované 1.out až 8.out a umiestnené v koreňovom adresári zipu. Za každý výstup, ktorý sa v zipe naozaj bude nachádzať a bude úplne správny, dostanete dva body.

Formát výstupu: pre každý test vypíšte \(n\) riadkov a v každom \(n\) čísel: čísla vo výslednej tabuľke, pričom namiesto čísel, ktoré ste “dali het” (čítaj: z tabuľky odstránili) vypíšte nuly.

Môžete vypisovať aj nadbytočné medzery a voľné riadky medzi výstupmi pre jednotlivé testy, náš testovač ich spokojne odignoruje. Ak existuje pre nejakú tabuľku viacero riešení, môžete vypísať ľubovoľné jedno z nich.

Posledné nanajvýš 4 body za úlohu udelíme za popis toho, ako ste úlohu riešili, a obzvlášť programu/ov, ktoré ste použili. Rozumne podrobný popis ľubovoľného postupu, ktorý nejaké vstupy naozaj vyriešil, môže dostať aspoň 3 body.

Príklady

Input:

1
5
15 12 14 14 24 
10 20 18 14 17
7 3 2 5 1
3 5 4 3 3
5 3 3 9 5
5 6 4 3 4
4 9 8 8 7

Output:

7 0 2 5 1
3 5 4 0 0
0 0 0 9 5
0 6 4 0 4
0 9 8 0 7