¡Eres un juez, otra vez! El concurso que estás juzgando incluye el siguiente problema:

"Tienes un triominó en forma de L de cada uno de los $\frac{4^n-1}{3}$ colores diferentes. Cubre una cuadrícula de $2^n$ por $2^n$ usando cada uno de estos triominós de tal manera que haya exactamente un cuadrado vacío y todos los demás cuadrados estén cubiertos por exactamente un cuadrado de dicho triominó. Todos los triominós deben ser utilizados."

Tu equipo debe escribir un verificador para este problema. La validación de los valores y el formato de entrada ya se ha realizado. Se te proporcionará un supuesto recubrimiento de una cuadrícula de $2^n$ por $2^n$, donde cada cuadrado en la cuadrícula es $0$ o un número entero positivo de $1$ a $\frac{4^n-1}{3}$ que representa uno de los colores. Determina si es, de hecho, un recubrimiento de la cuadrícula con $\frac{4^n-1}{3}$ triominós únicos y un único espacio vacío.

Los triominós en forma de L se ven así:

Entrada

La primera línea de la entrada contiene un único número entero $n$ ($1 \le n \le 10$), que es el $n$ de la descripción.

Cada una de las siguientes $2^n$ líneas contiene $2^n$ números enteros $x$ ($0 \le x \le \frac{4^n-1}{3}$), donde $0$ representa un espacio vacío, y cualquier número positivo es un identificador único de un triominó.

Salida

Imprime un único número entero, que es $1$ si la cuadrícula dada está cubierta con $\frac{4^n-1}{3}$ triominós únicos y un único espacio vacío. De lo contrario, imprime $0$.

Ejemplos

Entrada 1

2
1 1 2 2
1 3 3 2
4 4 3 5
4 0 5 5

Salida 1

1

Entrada 2

1
1 1
1 1

Salida 2

0