Một sự thật ít người biết về loài bò là chúng rất thích giải đố! Nhân dịp sinh nhật Bessie, Farmer John tặng cô một câu đố cơ khí thú vị để giải. Câu đố gồm ba vật thể rắn, mỗi vật thể được tạo thành từ các ô vuông đơn vị \(1 \times 1\) dán với nhau. Mỗi vật thể là một hình "liên thông", theo nghĩa là ta có thể đi từ một ô vuông bất kỳ của vật thể đến bất kỳ ô vuông nào khác trên cùng vật thể bằng cách bước qua các ô thuộc vật thể theo hướng bắc, nam, đông hoặc tây.

Một vật thể có thể được di chuyển bằng cách trượt nó lặp đi lặp lại một đơn vị về phía bắc, nam, đông hoặc tây. Mục tiêu của câu đố là di chuyển các vật thể sao cho chúng tách rời nhau, tức là các hình chữ nhật bao của chúng không giao nhau. Với hình dạng và vị trí của ba vật thể, nhiệm vụ của bạn là giúp Bessie xác định liệu có thể tách chúng ra hay không. Một cấu hình không thể tách rời được gọi là bị khóa.

Lưu ý: Những chương trình không làm gì ngoài việc đoán ngẫu nhiên dữ liệu ra có thể bị loại và nhận số điểm bằng không.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N1\), \(N2\) và \(N3\), cách nhau bởi dấu cách, lần lượt mô tả số ô vuông đơn vị tạo nên vật thể 1, 2 và 3.
• Các dòng từ 2 đến \(1+N1\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 1. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1\) đến \(1+N1+N2\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 2. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1+N2\) đến \(1+N1+N2+N3\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 3. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.

Dữ liệu ra

• Dòng 1: In ra 1 nếu có thể tách các vật thể khỏi nhau, hoặc 0 nếu chúng bị khóa.

Ví dụ

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

1

Nguồn

USACO 2012 US Open, Bronze Division — Unlocking Blocks

Tác giả: Brian Dean, 2012.