Problem description


Kwadrat magiczny
(kwadrat-magiczny)
Limit pamięci: 256 MB
Limit czasu: 4.00 s

Jasio w czasopiśmie z zagadkami odnalazł zagadkę uzupełnienia pól kwadratu magicznego. Bardzo spodobała mu się ta zagadka oraz ogólnie koncept kwadratów magicznych. Kwadrat magiczny to plansza składająca się z N × N pól. W każdym polu znajduje się liczba naturalna. Wszystkie sumy liczb w każdym rzędzie i w każdej kolumnie są sobie równe.

Jasio chciałby stworzyć swój własny kwadrat magiczny. Okazuje się nie być to takie proste. Zawsze jakaś suma mu się nie zgadza, a zmieniając pojedynczą liczbę Jasio psuje inne sumy, które już się ze sobą zgadzały. Celem Jasia jest, żeby suma każdego wiersza i każdej kolumny była równa dokładnie M. Postanowił poprosić Cię o pomoc w zamienieniu liczb z niektórych pól jego planszy na zera, aby to osiągnąć. Czy pomożesz mu w tym zadaniu?

Napisz program, który: wczyta opis planszy Jasia oraz założoną przez niego wartość M, wyznaczy zbiór pól, które należy zamienić na zera, aby osiągnąć kwadrat magiczny, w którym suma każdego wiersza i suma każdej kolumny jest równa dokładnie M i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M, oddzielone pojedynczym odstępem. Określają one kolejno rozmiar planszy oraz oczekiwaną przez Jasia sumę każdego wiersza i kolumny. W kolejnych N wierszach znajduje się po N liczb naturalnych Ai, j pooddzielanych pojedynczymi odstępami. Są to liczby zapisane na planszy Jasia.

Możesz założyć, że testy są tak dobrane, że każdy ma co najmniej jedno rozwiązanie. Jeżeli istnieje wiele poprawnych rozwiązań, Twój program może wypisać dowolne z nich.

Wyjście

Twój program powinien wypisać na wyjście N wierszy, w każdym z nich po N liczb pooddzielanych pojedynczymi odstępami – planszę reprezentująca kwadrat magiczny po zmianie niektórych wartości na zera.

Ograniczenia

1 ≤ N ≤ 12, 1 ≤ M ≤ 10 000, 1 ≤ Ai, j ≤ 10 000.

Przykład

Wejście Wyjście
3 10
6 5 4
2 8 7
2 2 6
6 0 4 
2 8 0 
2 2 6