G - Wymiary

Po odkryciu istnienia dodatkowych wymiarów przestrzennych królestwo Sześcianów idąc z duchem czasu rozpoczęło rozwój wielowymiarowego przemysłu. I tak powstały różne (wielowymiarowe rzecz jasna) maszyny, które swoją pracę wykonują na wielowymiarowych blokach. Oprócz wielu zalet, jakie niesie ze sobą wielowymiarowy świat, na jaw wyszły również pewne problemy, które problemami w starych dobrych trzech wymiarach się nie wydawały.

W wielowymiarowej fabryce pracuje wielowymiarowa krajalnica, która kroi wielowymiarowe hiperprostopadłościany (n-wymiarowy prostopadłościan to odpowiednik 3-wymiarowego prostopadłościanu w n-wymiarowym świecie). Wielowymiarowa krajalnica wykonuje kolejne cięcia hiperprostopadłościanu używając wielowymiarowego (supercienkiego) noża. Każde cięcie jest wykonywane równolegle do którejś ze ścian hiperprostopadłościanu i powoduje przecięcie go na dwa mniejsze hiperprostopadłościany.

Niech n-objętość hiperprostopadłościanu będzie oznaczała n-wymiarowy odpowiednik (normalnej 3-wymiarowej) objętości. Dla danej liczby wymiarów wszechświata, długości ścian początkowego hiperprostopadłościanu, oraz pozycji cięć wyznacz n-objętość największego hiperprostopadłościanu (nieprzeciętego, oczywiście) spośród tych, na które owa hiperbryła została przecięta.

Wejście

W pierwszej linii pliku wejściowego znajduje się jedna liczba naturalna oznaczająca liczbę następujących zestawów danych.

W pierwszej linii zestawu danych znajduje się liczba d (2 <= d <= 9) oznaczająca liczbę wymiarów we wrzechświecie. W kolejnej linii znajduje się d liczb naturalnych size[i] (1 <= size[i] <= 1000) oznaczających długości boków hiperprostopadłościanu w kolejnych wymiarach. Dalej następuje d linii opisujących cięcia krajalnicy w kolejnych wymiarach:

W i-tej linii znajduje się najpierw liczba n[i] oznaczająca liczbę cięć wykonanych przez krajalnicę w i-tym wymiarze. Następnie następuje ciąg n[i] (0 <= n[i] <= 10000) liczb c[i][j] (1 <= c[i][j] < size[i]) oznaczających odległość liczoną od pewnego (ustalonego) wierzchołka bryły, gdzie nastąpiło cięcie (w i-tym wymiarze, naturalnie).

Wyjście

Dla każdego zestawu danych Twój program powinien obliczyć n-objętość największego powstałego hiperprostopadłościanu (zgodnie z treścią zadania). W i-tej linii pliku wyjściowego powinna znaleźć się dokładnie jedna liczba całkowita oznaczająca resztę z dzielenia obliczonej n-objętości przy dzieleniu przez 10.

Przykładowe wejście

1
2
10 15
5 2 8 5 9 8
4 9 6 4 3

Przykładowe wyjście

8