Archiwum zadań programistycznych WWSI

Jak wiadomo Euro 2012 zbliża się dużymi krokami. Powstają nowe autostrady, hotele i stadiony - no może z małym wyjątkiem. Otóż w jednym z miast grunt, na którym ma powstać stadion podzielony jest na wiele małych działek, a każda z nich należy do innego właściciela. Osoby te bardzo chętnie odsprzedałyby swoje działki gdyby tylko znały ich ceny. Niestety, nie wszyscy je znają. Część z nich doskonale zna cenę swojego gruntu, lecz pozostali wiedzą jedynie jak wartość ich działki ma się do wartości działki kogoś innego lub jak wartość ich działki zmieniała się na przestrzeni czasu. Sytuacja jest niezwykle skomplikowana, harmonogram napięty, a osoba A wciąż twierdzi że jego działka jest warta tyle co działka osoby B + działka osoby C - działka osoby D i taniej jej nie sprzeda! Z kolei osoba X mówi, że jego działka najpierw zyskała na wartości 10, później straciła 3, no i do tego należy doliczyć wartość działki Y. Pomóż! Napisz program, który obliczy ile warta jest każda z działek i kwotę jaką musi wydać miasto na wykup ziemi.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 1700) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajdują się dwie liczby naturalne n i m (1 ≤ n, m ≤ 100) opisujące rozmiary gruntu. Zakładamy, że każda działka ma powierzchnię 1 × 1. W kolejnych n liniach znajduje się m opisów cen działek pooddzielanych spacjami. Każdy opis wartości gruntu może składać się z liczb naturalnych, odwołań do cen innej działki i operatorów matematycznych "+" i "-". Odwołanie do ceny innej działki ma postać "[w,k]" gdzie w (0 ≤ w < n) to numer wiersza zaś k (0 ≤ k < m) to numer kolumny, w której znajduje się cena działki. Przykładowo zapis: [1,1]+[2,3]-[23,3]+5 oznacza: cena działki w pierwszym wierszu i pierwszej kolumnie + wartość ziemi w drugim wierszu i trzeciej kolumnie - wartość działki z wiersza dwudziestego trzeciego w kolumnie trzeciej + pięć. Zakładamy, że wartość działki zawsze będzie liczbą dodatnią.

Wyjście

Dla każdego zestawu danych należy wypisać w n wierszach po m liczb będących cenami poszczególnych działek. W wierszu n+1 powinna zostać wypisana sumaryczna wartość całego gruntu. W przypadku gdy obliczenie wszystkich wartości działek jest niemożliwe na wyjściu należy wypisać tylko słowo "NIE".

Przykład

Wejście:

2
2 3
5 [0,0]+1 2+[0,1]
[0,2]+3 [1,0]-3 [1,1]-2
1 2
[0,1]+1 [0,0]-1

Wyjście:

5 6 8 
11 8 6 
44
NIE