有一款名為 Civilizations 的新遊戲正在開發中（請勿與 Civilization 混淆）。身為團隊中的資深開發人員，你的任務是編寫主要的遊戲引擎。

世界被劃分為 $n$ 列 $n$ 行的單位格。第 $i$ 列第 $j$ 行的單位格最初由文明 $p_{i,j}$ 所擁有（你可以假設在 $0$ 到 $n^2 - 1$ 之間的每個整數都對應一個文明。當然，在任何給定時間，許多文明可能不擁有任何土地），並且具有值 $v_{i,j}$，這對應於與該單位格相關的寶貴資源（或財務負債）。

對於給定的文明 $p$，我們定義兩個重要的衡量指標：其財富 ($w_p$) 和邊界長度 ($l_p$)。文明的財富是其所擁有土地的總價值，而邊界長度則是無序土地對 $\{a, b\}$ 的數量，使得 $a$ 和 $b$ 相鄰，且其中恰好有一個由 $p$ 擁有。

遊戲引擎必須處理一系列事件；在每個事件中，由於兩個文明之間的戰爭，其中一個單位的擁有者會發生改變。這種擁有者的變更至少會持續到下一次戰爭。在每次事件之後，引擎應確定當前最強大的文明（僅計算擁有至少一個單位的文明）有多強大。

遊戲設計團隊已經決定，文明 $p$ 的力量將計算為 $Aw_p + Bl_p + Cw_p l_p$。然而，棘手的地方在於：隨著遊戲世界局勢的發展，力量的定義也會隨之改變！在每次事件之後，你的引擎將會獲得用於計算係數 $A$、$B$ 和 $C$ 的新數值。

當然，你的引擎也必須足夠快速——否則 Civilizations 的玩家會感到厭煩！

輸入格式

輸入的第一行包含測試案例的數量 $z$ ($1 \le z \le 5000$)。接著是各個測試案例的描述。 每個測試案例的第一行包含一個整數 $n$ ($2 \le n \le 500$)，代表世界的大小。 接下來的 $n$ 行，每行包含 $n$ 個整數，描述單位格的值 $v_{i,j}$ ($|v_{i,j}| \le 100$)。 接下來的 $n$ 行，每行包含 $n$ 個整數，描述初始的單位格擁有者 $p_{i,j}$ ($0 \le p_{i,j} < n^2$)。 接下來的一行包含一個整數 $q$ ($1 \le q \le 10^5$)，代表事件的數量。 接下來的 $q$ 行描述這些事件。每行包含六個整數：$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$)，分別對應：發生擁有者變更的單位格之列與行、新的擁有者文明，以及用於計算文明力量的新係數。保證在事件發生前，文明 $p$ 並未擁有該單位格 $(i, j)$。

所有測試案例中的單位格總數不超過 $500\,000$。 所有測試案例中的查詢總數不超過 $200\,000$。

輸出格式

對於每個測試案例，輸出單行包含 $q$ 個整數：每次事件後最強大文明的力量值。

範例

輸入 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

輸出 1

5 -7 -2 10 20 -10

說明

在第一次事件後，文明 2 僅擁有 $(2, 1)$ 單位格，而文明 1 擁有其餘部分。兩個文明的邊界長度均為 2，財富分別為 7 和 3。力量為 5 的文明 1 是最強大的。

在第二次事件後，文明 1 擁有對角線上的單位格，而文明 2 擁有另一條對角線上的單位格。兩個文明的邊界長度均為 4，財富均為 5，因此它們的力量相等，均為 -7。

在第三次事件後，棋盤上現在有三個文明：1、2 和 3。文明 6 現在是最強大的。

最後，在最後三次事件中，文明 3 接管了剩餘的單位格。請注意，現在 3 對於任何 $A$、$B$ 和 $C$ 都是最強大的文明，因為我們只考慮控制至少一個單位格的文明。在遊戲結束時，文明 3 的力量為 -10，因為它的邊界長度為 0，財富為 10。