有一款新的热门游戏正在开发中：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。文明 1 的力量为 5，是最强大的。

在第二次事件后，文明 1 拥有对角线上的单元格，而文明 2 拥有另一条对角线上的单元格。两个文明的边界长度均为 4，财富均为 5，因此它们的力量相等，均为 -7。

在第三次事件后，棋盘上现在有三个文明：1、2 和 3。此时文明 6 是最强大的。

最后，在最后三次事件中，文明 3 接管了剩余的单元格。注意，现在对于任何 $A, B$ 和 $C$，3 都是最强大的文明，因为我们只考虑控制至少一个单元格的文明。游戏结束时文明 3 的力量为 -10，因为它拥有 0 的边界长度和 10 的财富。