문명

개발 중인 새로운 인기 게임 Civilizations (Civilization과 혼동하지 말 것)의 메인 게임 엔진을 작성하는 것이 팀의 Senior Developers 중 한 명인 당신의 일이다. 세계는 $n$개의 행과 $n$개의 열로 나뉜 단위 칸으로 이루어진다. $i$행 $j$열의 칸은 처음에 문명 $p_{i,j}$가 소유하고 있으며, 가치 $v_{i,j}$를 가진다. 이 값은 칸에 딸린 귀중한 자원(또는 재정적 부채)에 대응한다. ($0$ 이상 $n^2 - 1$ 이하의 모든 정수마다 그 정수에 대응하는 문명이 하나씩 있다고 가정해도 된다. 물론 어느 시점에든 그중 많은 문명이 칸을 하나도 소유하지 않을 수 있다.)

문명 $p$에 대해 두 가지 측도를 정의한다. 재산 $w_p$와 국경 길이 $l_p$이다. 문명의 재산은 그 문명이 소유한 칸들의 가치의 합이다. 국경 길이는 변을 공유하는 칸의 비순서쌍 $\{a, b\}$ 중 정확히 한 칸만 $p$가 소유한 쌍의 개수이다.

엔진은 이벤트의 연속을 처리해야 한다. 각 이벤트에서는 두 문명 사이의 전쟁 결과로 칸 하나의 소유자가 바뀐다. 소유자의 변경은 다음 전쟁이 일어날 때까지 유지된다. 이벤트마다 엔진은 현재 가장 강한 문명의 세력을 구해야 한다. 칸을 하나 이상 소유한 문명만 고려한다. 문명 $p$의 세력은 $A w_p + B l_p + C w_p l_p$로 계산한다. 다만 세계의 상황이 전개되면서 세력의 정의가 바뀐다. 이벤트마다 엔진에는 새로운 계수 $A$, $B$, $C$ 값이 주어진다. 엔진은 빨라야 한다. 그렇지 않으면 Civilizations 플레이어들이 지루해할 것이다.

입력의 첫 줄에는 테스트 케이스의 개수 $z$ ($1 \leq z \leq 5000$)가 주어진다. 이어서 테스트 케이스들이 주어진다. 각 테스트 케이스의 첫 줄에는 세계의 크기 $n$ ($2 \leq n \leq 500$) 하나가 주어진다. 다음 $n$개의 줄에는 각각 $n$개의 정수가 주어지며, 칸의 값 $v_{i,j}$ ($|v_{i,j}| \leq 100$)를 나타낸다. 그다음 $n$개의 줄에는 각각 $n$개의 정수가 주어지며, 처음의 소유자 $p_{i,j}$ ($0 \leq p_{i,j} < n^2$)를 나타낸다. 다음 줄에는 이벤트의 개수 $q$ ($1 \leq q \leq 10^5$) 하나가 주어진다. 이어지는 $q$개의 줄은 이벤트를 나타낸다. 각 줄에는 여섯 정수 $i$, $j$, $p$, $A$, $B$, $C$가 주어진다 ($1 \leq i, j \leq n$; $0 \leq p < n^2$; $|A| \leq 10^{10}$; $|B| \leq 10^{12}$; $|C| \leq 10^4$). 각각 소유자가 바뀌는 칸의 행과 열, 칸의 새 소유 문명, 문명의 세력을 계산할 새 계수를 나타낸다. 이벤트 이전에 문명 $p$는 칸 $(i, j)$를 소유하지 않았음이 보장된다. 모든 테스트 케이스의 칸 수의 합은 $500\,000$을 넘지 않는다. 모든 테스트 케이스의 쿼리 수의 합은 $200\,000$을 넘지 않는다.

각 테스트 케이스마다 한 줄에 $q$개의 정수를 출력한다. 각 정수는 해당 이벤트 이후 가장 강한 문명의 세력 값이다.

첫 번째 이벤트 후 문명 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이기 때문이다.