Một trò chơi mới đang được phát triển: Civilizations (không nên nhầm lẫn với Civilization). Là một trong những Lập trình viên cấp cao trong nhóm, công việc của bạn là viết bộ máy trò chơi chính.

Thế giới được chia thành $n$ hàng và $n$ cột các ô đơn vị. Ô đơn vị ở hàng thứ $i$ và cột thứ $j$ ban đầu thuộc sở hữu của nền văn minh $p_{i,j}$ (bạn có thể giả định rằng với mọi số nguyên từ $0$ đến $n^2 - 1$ bao gồm cả hai, đều có một nền văn minh tương ứng với số nguyên đó. Tất nhiên, tại bất kỳ thời điểm nào, nhiều nền văn minh có thể không sở hữu bất kỳ ô nào), và có giá trị $v_{i,j}$, tương ứng với các tài nguyên quý giá (hoặc nợ tài chính) liên quan đến nó.

Đối với một nền văn minh $p$ nhất định, chúng ta định nghĩa hai thước đo quan trọng: sự giàu có ($w_p$) và độ dài biên giới ($l_p$). Sự giàu có của một nền văn minh là tổng giá trị của các ô mà nó sở hữu, trong khi độ dài biên giới là số lượng các cặp ô không thứ tự $\{a, b\}$ sao cho $a$ và $b$ chung một cạnh, và chính xác một trong hai ô đó thuộc sở hữu của $p$.

Bộ máy trò chơi sẽ phải xử lý một chuỗi các sự kiện; trong mỗi sự kiện, chủ sở hữu của một trong các ô thay đổi, là kết quả của một cuộc chiến giữa hai nền văn minh. Sự thay đổi chủ sở hữu là vĩnh viễn, ít nhất là cho đến cuộc chiến tiếp theo. Sau mỗi sự kiện như vậy, bộ máy cần xác định nền văn minh quyền lực nhất hiện tại là bao nhiêu (chỉ tính các nền văn minh sở hữu ít nhất một ô).

Nhóm thiết kế trò chơi đã quyết định rằng sức mạnh của nền văn minh $p$ sẽ được tính là $Aw_p + Bl_p + C$. Mọi thứ trở nên phức tạp ở đây: định nghĩa về sức mạnh thay đổi khi tình hình trong thế giới trò chơi phát triển! Sau mỗi sự kiện, bộ máy của bạn sẽ được cung cấp các giá trị mới cho các hệ số $A$, $B$ và $C$.

Tất nhiên, bộ máy của bạn cũng phải nhanh – nếu không, người chơi Civilizations sẽ cảm thấy nhàm chán!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng các bộ kiểm thử $z$ ($1 \le z \le 5000$). Các mô tả của các bộ kiểm thử theo sau.

Dòng đầu tiên của mỗi bộ kiểm thử bao gồm một số nguyên duy nhất $n$ ($2 \le n \le 500$) – kích thước của thế giới.

$n$ dòng tiếp theo chứa $n$ số nguyên mỗi dòng, mô tả các giá trị ô $v_{i,j}$ ($|v_{i,j}| \le 100$).

$n$ dòng tiếp theo chứa $n$ số nguyên mỗi dòng, mô tả chủ sở hữu ban đầu của các ô $p_{i,j}$ ($0 \le p_{i,j} < n^2$).

Dòng tiếp theo bao gồm một số nguyên duy nhất $q$ ($1 \le q \le 10^5$) – số lượng sự kiện.

$q$ dòng tiếp theo mô tả các sự kiện. Mỗi dòng chứa sáu số nguyên: $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$), tương ứng với: hàng và cột của ô thay đổi chủ sở hữu, nền văn minh sở hữu mới, và các hệ số mới để tính sức mạnh của các nền văn minh. Đảm bảo rằng trước sự kiện, nền văn minh $p$ không sở hữu ô $(i, j)$.

Tổng số ô đơn vị trong tất cả các bộ kiểm thử không vượt quá $500\,000$.

Tổng số truy vấn trong tất cả các bộ kiểm thử không vượt quá $200\,000$.

Dữ liệu ra

Đối với mỗi bộ kiểm thử, hãy xuất ra một dòng duy nhất chứa $q$ số nguyên: giá trị sức mạnh của nền văn minh quyền lực nhất sau mỗi sự kiện.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

5 -7 -2 10 20 -10

Ghi chú

Sau sự kiện đầu tiên, nền văn minh 2 chỉ sở hữu ô $(2, 1)$, trong khi nền văn minh 1 sở hữu phần còn lại. Cả hai nền văn minh đều có độ dài biên giới là 2, và sự giàu có của chúng lần lượt là 7 và 3. Nền văn minh 1 với sức mạnh là 5 là nền văn minh quyền lực nhất.

Sau sự kiện thứ hai, nền văn minh 1 sở hữu các ô trên một đường chéo, trong khi nền văn minh 2 sở hữu các ô trên đường chéo còn lại. Cả hai nền văn minh đều có độ dài biên giới là 4, và sự giàu có là 5, vì vậy chúng có sức mạnh ngang nhau với sức mạnh là -7.

Sau sự kiện thứ ba, hiện có ba nền văn minh trên bàn cờ: 1, 2 và 3. Nền văn minh 6 hiện là nền văn minh quyền lực nhất.

Cuối cùng, trong ba sự kiện cuối cùng, nền văn minh 3 chiếm lấy các ô còn lại. Lưu ý rằng bây giờ 3 là nền văn minh quyền lực nhất cho bất kỳ $A, B$ và $C$ nào, vì chúng ta chỉ tính đến các nền văn minh kiểm soát ít nhất một ô. Sức mạnh của nền văn minh 3 vào cuối trò chơi là -10, vì nó có độ dài biên giới là 0 và sự giàu có là 10.