Un nouveau jeu est en cours de développement : Civilizations (à ne pas confondre avec Civilization). En tant que l'un des développeurs seniors de l'équipe, votre travail consiste à écrire le moteur principal du jeu.

Le monde est divisé en $n$ lignes et $n$ colonnes de cases unitaires. La case située à la $i$-ième ligne et à la $j$-ième colonne est initialement possédée par une civilisation $p_{i,j}$ (vous pouvez supposer que pour chaque entier compris entre $0$ et $n^2 - 1$ inclus, il existe une civilisation correspondant à cet entier. Bien sûr, à tout moment, beaucoup d'entre elles peuvent ne posséder aucune case), et a une valeur $v_{i,j}$, qui correspond aux ressources précieuses (ou passifs financiers) qui lui sont associées.

Pour une civilisation donnée $p$, nous définissons deux mesures importantes : sa richesse ($w_p$) et la longueur de ses frontières ($l_p$). La richesse d'une civilisation est la valeur totale des cases qu'elle possède, tandis que la longueur des frontières est le nombre de paires non ordonnées de cases $\{a, b\}$ telles que $a$ et $b$ partagent un côté, et qu'exactement l'une d'entre elles soit possédée par $p$.

Le moteur de jeu devra gérer une séquence d'événements ; dans chacun d'eux, le propriétaire de l'une des cases change, à la suite d'une guerre entre deux civilisations. Le changement de propriétaire est permanent, au moins jusqu'à la prochaine guerre. Après chaque événement, le moteur doit déterminer la puissance de la civilisation la plus puissante actuellement (en ne comptant que les civilisations qui possèdent au moins une case).

L'équipe de conception du jeu a déjà décidé que la puissance de la civilisation $p$ sera calculée comme $Aw_p + Bl_p + Cw_p l_p$. C'est là que les choses se compliquent : la définition de la puissance change à mesure que la situation dans le monde du jeu évolue ! Après chaque événement, votre moteur recevra de nouvelles valeurs pour les coefficients $A$, $B$ et $C$.

Bien sûr, votre moteur doit également être rapide, sinon les joueurs de Civilizations s'ennuieront !

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 5000$). Les descriptions des cas de test suivent.

La première ligne de chaque cas de test consiste en un entier unique $n$ ($2 \le n \le 500$) – la taille du monde.

Les $n$ lignes suivantes contiennent $n$ entiers chacune, et décrivent les valeurs des cases $v_{i,j}$ ($|v_{i,j}| \le 100$).

Les $n$ lignes suivantes contiennent $n$ entiers chacune, et décrivent les propriétaires initiaux des cases $p_{i,j}$ ($0 \le p_{i,j} < n^2$).

La ligne suivante consiste en un entier unique $q$ ($1 \le q \le 10^5$) – le nombre d'événements.

Les $q$ lignes suivantes décrivent les événements. Chacune contient six entiers : $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$), correspondant à : la ligne et la colonne de la case qui change de propriétaire, la nouvelle civilisation propriétaire, et les nouveaux coefficients pour calculer les puissances des civilisations, respectivement. Il est garanti qu'avant l'événement, la civilisation $p$ ne possédait pas la case $(i, j)$.

Le nombre total de cases unitaires dans tous les cas de test ne dépasse pas $500\,000$.

Le nombre total de requêtes dans tous les cas de test ne dépasse pas $200\,000$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant $q$ entiers : la valeur de puissance de la civilisation la plus puissante après chacun des événements.

Exemples

Entrée 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

Sortie 1

5 -7 -2 10 20 -10

Remarque

Après le premier événement, la civilisation 2 possède uniquement la case $(2, 1)$, tandis que la civilisation 1 possède le reste. Les deux civilisations ont des frontières de longueur 2, et leur richesse est respectivement de 7 et 3. La civilisation 1, avec une puissance de 5, est la plus puissante.

Après le deuxième événement, la civilisation 1 possède les cases sur une diagonale, tandis que la civilisation 2 possède celles sur l'autre. Les deux civilisations ont des frontières de longueur 4 et une richesse de 5, elles sont donc également puissantes avec une puissance de -7.

Après le troisième événement, il y a maintenant trois civilisations sur le plateau : 1, 2 et 3. La civilisation 6 est maintenant la plus puissante.

Enfin, lors des trois derniers événements, la civilisation 3 prend le contrôle des cases restantes. Notez que maintenant 3 est la civilisation la plus puissante pour n'importe quels $A, B$ et $C$, puisque nous ne prenons en compte que les civilisations contrôlant au moins une case. La puissance de la civilisation 3 à la fin du jeu est de -10, puisqu'elle a des frontières de longueur 0 et une richesse de 10.