Hay un nuevo juego en desarrollo: Civilizations (que no debe confundirse con Civilization). Como uno de los desarrolladores sénior del equipo, tu trabajo es escribir el motor principal del juego.

El mundo está dividido en $n$ filas y $n$ columnas de campos unitarios. El campo unitario en la fila $i$ y la columna $j$ es propiedad inicialmente de la civilización $p_{i,j}$ (puedes asumir que para cada número entero entre $0$ y $n^2 - 1$ inclusive, existe una civilización correspondiente a ese entero. Por supuesto, en cualquier momento dado, muchas de ellas pueden no poseer ningún campo), y tiene un valor $v_{i,j}$, que corresponde a los recursos preciosos (o pasivos financieros) asociados con él.

Para una civilización dada $p$, definimos dos medidas importantes: su riqueza ($w_p$) y la longitud de sus fronteras ($l_p$). La riqueza de una civilización es el valor total de los campos que posee, mientras que la longitud de las fronteras es el número de pares no ordenados de campos $\{a, b\}$, tales que $a$ y $b$ comparten un lado, y exactamente uno de ellos es propiedad de $p$.

El motor del juego tendrá que manejar una secuencia de eventos; en cada uno, el propietario de uno de los campos cambia, como resultado de una guerra entre dos civilizaciones. El cambio de propietario es permanente, al menos hasta la siguiente guerra. Después de cada evento, el motor debe determinar qué tan poderosa es la civilización más poderosa actual (contando solo las civilizaciones que poseen al menos un campo).

El equipo de diseño del juego ya ha decidido que el poder de la civilización $p$ se calculará como $Aw_p + Bl_p + C$. ¡Aquí es donde las cosas se complican: la definición de poder cambia a medida que la situación en el mundo del juego se desarrolla! Después de cada evento, tu motor recibirá nuevos valores para los coeficientes $A$, $B$ y $C$.

¡Por supuesto, tu motor también tiene que ser rápido; de lo contrario, los jugadores de Civilizations se aburrirán!

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 5000$). Siguen las descripciones de los casos de prueba.

La primera línea de cada caso de prueba consiste en un solo entero $n$ ($2 \le n \le 500$) – el tamaño del mundo.

Las siguientes $n$ líneas contienen $n$ enteros cada una, y describen los valores de los campos $v_{i,j}$ ($|v_{i,j}| \le 100$).

Las siguientes $n$ líneas contienen $n$ enteros cada una, y describen los propietarios iniciales de los campos $p_{i,j}$ ($0 \le p_{i,j} < n^2$).

La siguiente línea consiste en un solo entero $q$ ($1 \le q \le 10^5$) – el número de eventos.

Las siguientes $q$ líneas describen los eventos. Cada una de ellas contiene seis enteros: $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$), correspondientes a: la fila y columna del campo que cambia de propietario, la nueva civilización propietaria, y los nuevos coeficientes para calcular los poderes de las civilizaciones, respectivamente. Se garantiza que antes del evento la civilización $p$ no poseía el campo $(i, j)$.

El número total de campos unitarios en todos los casos de prueba no supera los $500\,000$.

El número total de consultas en todos los casos de prueba no supera los $200\,000$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga $q$ enteros: el valor de poder de la civilización más poderosa después de cada uno de los eventos.

Ejemplos

Entrada 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

Salida 1

5 -7 -2 10 20 -10

Nota

Después del primer evento, la civilización 2 posee solo el campo $(2, 1)$, mientras que la civilización 1 posee el resto. Ambas civilizaciones tienen fronteras de longitud 2, y su riqueza es 7 y 3, respectivamente. La civilización 1 con un poder de 5 es la más poderosa.

Después del segundo evento, la civilización 1 posee campos en una diagonal, mientras que la civilización 2 en la otra. Ambas civilizaciones tienen fronteras de longitud 4, y una riqueza de 5, por lo que son igualmente poderosas con un poder de -7.

Después del tercer evento, ahora hay tres civilizaciones en el tablero: 1, 2 y 3. La civilización 6 es ahora la más poderosa.

Finalmente, en los últimos tres eventos, la civilización 3 toma el control de los campos restantes. Nota que ahora 3 es la civilización más poderosa para cualquier $A$, $B$ y $C$, ya que solo tomamos en cuenta a las civilizaciones que controlan al menos un campo. El poder de la civilización 3 al final del juego es -10, ya que tiene fronteras de longitud 0 y una riqueza de 10.