Bạn lại là giám khảo một lần nữa! Cuộc thi mà bạn đang chấm điểm bao gồm bài toán sau:

"Bạn có một quân domino hình chữ L (triomino) cho mỗi màu trong số $\frac{4^n-1}{3}$ màu khác nhau. Hãy lát một lưới $2^n \times 2^n$ bằng cách sử dụng mỗi quân triomino này sao cho có đúng một ô trống và tất cả các ô khác đều được bao phủ bởi đúng một ô của một quân triomino như vậy. Tất cả các quân triomino phải được sử dụng."

Nhóm của bạn cần viết một trình kiểm tra cho bài toán này. Việc xác thực các giá trị đầu vào và định dạng đã được thực hiện. Bạn sẽ được cung cấp một cách lát lưới $2^n \times 2^n$ giả định, trong đó mỗi ô trong lưới là $0$ hoặc một số nguyên dương từ $1$ đến $\frac{4^n-1}{3}$ đại diện cho một trong các màu. Hãy xác định xem đó có thực sự là một cách bao phủ lưới bằng $\frac{4^n-1}{3}$ quân triomino duy nhất và một ô trống duy nhất hay không.

Các quân triomino hình chữ L trông như thế này:

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($1 \le n \le 10$), là giá trị $n$ trong mô tả.

Mỗi dòng trong số $2^n$ dòng tiếp theo chứa $2^n$ số nguyên $x$ ($0 \le x \le \frac{4^n-1}{3}$), trong đó $0$ đại diện cho một ô trống, và bất kỳ số dương nào là một định danh duy nhất của một quân triomino.

Dữ liệu ra

In ra một số nguyên duy nhất, là $1$ nếu lưới đã cho được bao phủ bởi $\frac{4^n-1}{3}$ quân triomino duy nhất và một ô trống duy nhất. Ngược lại, in ra $0$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Dữ liệu vào 2

1
1 1
1 1

Dữ liệu ra 2

0