開発中の新しいホットなゲーム『Civilizations』（『Civilization』とは別物です）において、シニア開発者の一人であるあなたの仕事は、メインのゲームエンジンを作成することです。

世界は $n$ 行 $n$ 列のユニットフィールドに分割されています。$i$ 行 $j$ 列のユニットフィールドは、初期状態では文明 $p_{i,j}$ が所有しています（$0$ から $n^2 - 1$ までのすべての整数に対して、その整数に対応する文明が存在すると仮定して構いません。もちろん、ある時点で多くの文明はフィールドを一つも所有していない可能性があります）。また、各フィールドにはそのフィールドに関連する貴重な資源（または負債）に対応する値 $v_{i,j}$ が設定されています。

ある文明 $p$ に対して、2つの重要な指標を定義します。それは「富（$w_p$）」と「境界の長さ（$l_p$）」です。文明の富とは、その文明が所有するフィールドの値の合計であり、境界の長さとは、隣接するフィールドのペア $\{a, b\}$ であって、一方が文明 $p$ に所有され、もう一方が文明 $p$ に所有されていないものの個数です。

ゲームエンジンは一連のイベントを処理する必要があります。各イベントでは、2つの文明間の戦争の結果として、あるフィールドの所有者が変更されます。この所有者の変更は、少なくとも次の戦争までは永続的です。各イベントの後、エンジンは現在の「最も強力な文明」（少なくとも1つのフィールドを所有している文明のみを考慮）がどれほど強力であるかを判定しなければなりません。

ゲームデザインチームは、文明 $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$ 行はイベントを表します。各行には6つの整数 $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

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 が最も強力です。

2回目のイベントの後、文明 1 は一方の対角線上のフィールドを所有し、文明 2 はもう一方の対角線上のフィールドを所有します。両文明の境界の長さは 4 で、富は 5 であり、パワー -7 で同等に強力です。

3回目のイベントの後、ボード上には文明 1, 2, 3 の3つが存在します。このとき文明 6 が最も強力です。

最後に、最後の3つのイベントで、文明 3 が残りのフィールドをすべて占領します。少なくとも1つのフィールドを所有している文明のみを考慮するため、どのような $A, B, C$ に対しても文明 3 が最も強力な文明であることに注意してください。ゲーム終了時の文明 3 のパワーは、境界の長さが 0、富が 10 であるため -10 となります。