새로운 게임 Civilizations(게임 Civilization과는 다름)가 개발 중입니다. 팀의 선임 개발자 중 한 명으로서, 당신은 메인 게임 엔진을 작성해야 합니다.

세계는 $n$개의 행과 $n$개의 열로 이루어진 단위 필드로 나뉩니다. $i$번째 행, $j$번째 열의 단위 필드는 처음에 문명 $p_{i,j}$가 소유하고 있습니다($0$부터 $n^2-1$ 사이의 모든 정수에 대응하는 문명이 존재한다고 가정할 수 있습니다. 물론, 특정 시점에 많은 문명이 필드를 하나도 소유하지 않을 수도 있습니다). 각 필드에는 해당 필드와 관련된 귀중한 자원(또는 재정적 부채)에 해당하는 값 $v_{i,j}$가 있습니다.

특정 문명 $p$에 대해, 우리는 두 가지 중요한 척도인 부(wealth, $w_p$)와 경계의 길이(length of borders, $l_p$)를 정의합니다. 문명의 부는 그 문명이 소유한 필드들의 총 가치이며, 경계의 길이는 서로 인접한 두 필드의 순서 없는 쌍 $\{a, b\}$ 중 정확히 하나만 문명 $p$가 소유하고 있는 쌍의 개수입니다.

게임 엔진은 일련의 이벤트를 처리해야 합니다. 각 이벤트에서는 두 문명 간의 전쟁 결과로 필드 중 하나의 소유자가 변경됩니다. 소유자 변경은 최소한 다음 전쟁 전까지는 영구적입니다. 각 이벤트가 발생한 후, 엔진은 현재 가장 강력한 문명(적어도 하나의 필드를 소유한 문명만 고려)이 얼마나 강력한지 결정해야 합니다.

게임 디자인 팀은 문명 $p$의 힘(power)을 $Aw_p + Bl_p + C$로 계산하기로 결정했습니다. 하지만 여기서 문제가 복잡해집니다. 게임 세계의 상황이 전개됨에 따라 힘의 정의가 바뀝니다! 각 이벤트가 발생한 후, 엔진은 계수 $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$을 넘지 않습니다.

출력

각 테스트 케이스에 대해, 각 이벤트가 발생한 후 가장 강력한 문명의 힘 값을 포함하는 한 줄의 정수들을 출력하십시오.

예제

입력 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의 힘은 경계의 길이가 0이고 부가 10이므로 -10입니다.