Problem description

Farmer Dżon, który właśnie przeszedł na emeryturę, wreszcie ma dużo czasu, by zająć się swoją największą pasją – hodowlą szczurów. Niestety życie emeryta nie jest łatwe: zapasy paszy powoli się kończą, a jego podopieczni robią się coraz bardziej głodni.

Pewnego dnia Dżon znalazł na strychu stary, mocno postrzępiony dywan. Ku jego zaskoczeniu okazało się, że materiał, z którego został wykonany, jest prawdziwym przysmakiem dla szczurów. Problem polega jednak na tym, że nie każdy szczur jest w stanie zjeść dowolny fragment dywanu.

Dywan ma kształt prostokąta o wymiarach N × M i został podzielony na N ⋅ M kwadratów jednostkowych. Pole znajdujące się w wierszu i i kolumnie j ma grubość a_i, j.

Dla szczura o rozmiarze k obowiązują następujące zasady:

• jeśli a_i, j < k, szczur może swobodnie przejść przez dane pole, ale niczego nie zjada,
• jeśli a_i, j > 2k, pole jest zbyt grube i szczur nigdy na nie nie wejdzie,
• jeśli k ≤ a_i, j ≤ 2k, szczur może wejść na pole i zjeść a_i, j − k jednostek dywanu, redukując grubość dywanu w tym kwadracie do k.

Szczur rozpoczyna swoją wędrówkę poza dywanem. Może poruszać się pomiędzy sąsiednimi polami (góra, dół, lewo, prawo), a także dowolnie opuszczać dywan i wracać na niego w innym miejscu na brzegu. Może dowolnie wiele razy wchodzić na to samo pole, jednak po pierwszym wejściu grubość dywanu może być już zmieniona.

Farmer Dżon ma w hodowli Q szczurów i na razie nie wpuszcza żadnego z nich na dywan, ale chciałby wiedzieć ile maksymalnie jednostek dywanu mógłby zjeść każdy ze szczurów, gdyby został wpuszczony.

Wejście

W pierwszym wierszu znajduje się liczba zestawów testowych T. Opis zestawu testowego składa się z następujących wierszy:

• pierwszy wiersz zawiera dwie liczby całkowite N, M,
• kolejne N wierszy zawiera po M liczb całkowitych a_i, j opisujących grubości pól dywanu,
• następny wiersz zawiera liczbę szczurów Q,
• ostatni wiersz zawiera Q liczb k₁, k₂, …, k_Q, oznaczających rozmiary szczurów.

Wyjście

Dla każdego zestawu danych wypisz jeden wiersz zawierający Q liczb – maksymalną liczbę jednostek dywanu, które mógłby zjeść szczur o odpowiednim rozmiarze, gdyby został wpuszczony na dywan.

Ograniczenia

1 ≤ T ≤ 10⁴, 1 ≤ N ⋅ M ≤ 10⁶, 1 ≤ Q ≤ 10⁶, 1 ≤ a_i, j, k_i ≤ 10⁹.

Łączna liczba pól we wszystkich zestawach danych nie przekracza 10⁶.

Łączna liczba szczurów we wszystkich zestawach danych nie przekracza 10⁶.

Podzadania

Przykład

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

2 1 4 14 4 

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

0 33 
0 1 0 

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

13 4 0 27 32 4 32 37 13 
5 0 0 40 39 14 
14 0 19 50 52