Вы снова судья! Соревнование, которое вы судите, включает следующую задачу:

«У вас есть по одному L-образному триомино каждого из $\frac{4^n-1}{3}$ различных цветов. Замостите сетку $2^n$ на $2^n$, используя каждое из этих триомино так, чтобы осталась ровно одна пустая клетка, а все остальные клетки были покрыты ровно одной клеткой такого триомино. Все триомино должны быть использованы».

Ваша команда должна написать чекер для этой задачи. Проверка входных значений и формата уже выполнена. Вам будет предоставлено предполагаемое замощение сетки $2^n$ на $2^n$, где каждая клетка сетки содержит либо $0$, либо положительное целое число от $1$ до $\frac{4^n-1}{3}$, представляющее один из цветов. Определите, является ли это действительно покрытием сетки $\frac{4^n-1}{3}$ уникальными триомино и одной пустой клеткой.

L-образные триомино выглядят так:

Входные данные

Первая строка входных данных содержит единственное целое число $n$ ($1 \le n \le 10$), которое соответствует $n$ из описания.

Каждая из следующих $2^n$ строк содержит $2^n$ целых чисел $x$ ($0 \le x \le \frac{4^n-1}{3}$), где $0$ представляет пустую клетку, а любое положительное число является уникальным идентификатором триомино.

Выходные данные

Выведите единственное целое число: $1$, если данная сетка покрыта $\frac{4^n-1}{3}$ уникальными триомино и одной пустой клеткой, и $0$ в противном случае.

Примеры

Входные данные 1

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

Выходные данные 1

1

Входные данные 2

1
1 1
1 1

Выходные данные 2

0