W fazie rozwoju znajduje się nowa, gorąca gra: Civilizations (nie mylić z Civilization). Jako jeden z głównych programistów w zespole, masz za zadanie napisać główny silnik gry.

Świat jest podzielony na $n$ wierszy i $n$ kolumn pól jednostkowych. Pole w $i$-tym wierszu i $j$-tej kolumnie jest początkowo własnością cywilizacji $p_{i,j}$ (można założyć, że dla każdej liczby całkowitej od $0$ do $n^2 - 1$ włącznie istnieje odpowiadająca jej cywilizacja. Oczywiście w dowolnym momencie wiele z nich może nie posiadać żadnych pól) i ma wartość $v_{i,j}$, która odpowiada cennym zasobom (lub zobowiązaniom finansowym) z nim związanym.

Dla danej cywilizacji $p$ definiujemy dwie ważne miary: jej bogactwo ($w_p$) oraz długość granic ($l_p$). Bogactwo cywilizacji to całkowita wartość posiadanych przez nią pól, natomiast długość granic to liczba nieuporządkowanych par pól $\{a, b\}$, takich że $a$ i $b$ dzielą bok i dokładnie jedno z nich jest własnością cywilizacji $p$.

Silnik gry musi obsługiwać sekwencję zdarzeń; w każdym z nich zmienia się właściciel jednego z pól w wyniku wojny między dwiema cywilizacjami. Zmiana właściciela jest trwała, przynajmniej do następnej wojny. Po każdym takim zdarzeniu silnik powinien określić, jak potężna jest obecnie najpotężniejsza cywilizacja (uwzględniając tylko cywilizacje, które posiadają co najmniej jedno pole).

Zespół projektowy zdecydował już, że potęga cywilizacji $p$ będzie obliczana jako $Aw_p + Bl_p + Cw_pl_p$. Tutaj sprawa staje się skomplikowana: definicja potęgi zmienia się wraz z rozwojem sytuacji w świecie gry! Po każdym zdarzeniu Twój silnik otrzyma nowe wartości współczynników $A$, $B$ oraz $C$.

Oczywiście Twój silnik musi być również szybki – w przeciwnym razie gracze Civilizations zaczną się nudzić!

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych $z$ ($1 \le z \le 5000$). Następnie następują opisy zestawów danych.

Pierwsza linia każdego zestawu danych składa się z pojedynczej liczby całkowitej $n$ ($2 \le n \le 500$) – rozmiaru świata.

Następne $n$ linii zawiera po $n$ liczb całkowitych i opisuje wartości pól $v_{i,j}$ ($|v_{i,j}| \le 100$).

Następne $n$ linii zawiera po $n$ liczb całkowitych i opisuje początkowych właścicieli pól $p_{i,j}$ ($0 \le p_{i,j} < n^2$).

Następna linia składa się z pojedynczej liczby całkowitej $q$ ($1 \le q \le 10^5$) – liczby zdarzeń.

Następne $q$ linii opisuje zdarzenia. Każda z nich zawiera sześć liczb całkowitych: $i, j, p, A, B, C$ ($1 \le i, j \le n$; $0 \le p < n^2$; $|A| \le 10^{10}$; $|B| \le 10^{12}$; $|C| \le 10^4$), odpowiadających: wierszowi i kolumnie pola, którego właściciel się zmienia, nowej cywilizacji właściciela oraz nowym współczynnikom do obliczania potęg cywilizacji. Gwarantuje się, że przed zdarzeniem cywilizacja $p$ nie była właścicielem pola $(i, j)$.

Całkowita liczba pól jednostkowych we wszystkich zestawach danych nie przekracza $500\,000$.

Całkowita liczba zapytań we wszystkich zestawach danych nie przekracza $200\,000$.

Wyjście

Dla każdego zestawu danych wypisz pojedynczą linię zawierającą $q$ liczb całkowitych: wartość potęgi najpotężniejszej cywilizacji po każdym ze zdarzeń.

Przykład

Wejście 1

1
2
1 2
3 4
1 1
2 2
6
2 2 1 1 -1 0
1 2 2 1 2 -1
2 1 3 0 1 -1
1 2 3 2 0 0
1 1 3 1 1 1
2 2 3 -1 -1 -1

Wyjście 1

5 -7 -2 10 20 -10

Uwagi

Po pierwszym zdarzeniu cywilizacja 2 posiada tylko pole $(2, 1)$, podczas gdy cywilizacja 1 posiada resztę. Obie cywilizacje mają granice o długości 2, a ich bogactwo wynosi odpowiednio 7 i 3. Cywilizacja 1 z potęgą 5 jest najpotężniejsza.

Po drugim zdarzeniu cywilizacja 1 posiada pola na jednej przekątnej, podczas gdy cywilizacja 2 na drugiej. Obie cywilizacje mają granice o długości 4 i bogactwo 5, więc są równie potężne z potęgą -7.

Po trzecim zdarzeniu na planszy znajdują się teraz trzy cywilizacje: 1, 2 i 3. Cywilizacja 6 jest teraz najpotężniejsza.

Wreszcie, w ostatnich trzech zdarzeniach cywilizacja 3 przejmuje pozostałe pola. Zauważ, że teraz 3 jest najpotężniejszą cywilizacją dla dowolnych $A, B$ i $C$, ponieważ bierzemy pod uwagę tylko cywilizacje kontrolujące co najmniej jedno pole. Potęga cywilizacji 3 pod koniec gry wynosi -10, ponieważ ma ona granice o długości 0 i bogactwo 10.