Ít ai biết bò rất thích câu đố! Nhân sinh nhật Bessie, Farmer John tặng cô câu đố cơ học thú vị. Gồm ba vật rắn, mỗi vật từ các ô vuông đơn vị $1\times1$ dán lại. Mỗi hình «liên thông»: từ bất kỳ ô nào đến được mọi ô khác bằng bước bắc, nam, đông hoặc tây qua các ô của vật.

Vật di chuyển bằng cách trượt liên tiếp một đơn vị về bắc, nam, đông hoặc tây. Mục tiêu là tách các vật để hộp bao của chúng đôi một không giao nhau. Cho hình dạng và vị trí ba vật, giúp Bessie xác định có tách được không. Cấu hình không tách được gọi là khóa.

[Lưu ý: chương trình chỉ đoán ngẫu nhiên đầu ra có thể bị loại và nhận không điểm.]

Dữ liệu vào

• Dòng 1: ba số nguyên $N1$, $N2$, $N3$ cách nhau bởi dấu cách, lần lượt là số ô đơn vị của vật 1, 2, 3.
• Dòng $2\ldots1+N1$: mỗi dòng mô tả tọa độ $(x,y)$ góc tây nam của một ô thuộc vật 1. Mọi tọa độ trong $0\ldots9$.
• Dòng $2+N1\ldots1+N1+N2$: mỗi dòng mô tả tọa độ $(x,y)$ góc tây nam của một ô thuộc vật 2. Mọi tọa độ trong $0\ldots9$.
• Dòng $2+N1+N2\ldots1+N1+N2+N3$: mỗi dòng mô tả tọa độ $(x,y)$ góc tây nam của một ô thuộc vật 3. Mọi tọa độ trong $0\ldots9$.

Dữ liệu ra

• Dòng 1: in 1 nếu tách được, hoặc 0 nếu bị khóa.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Ghi chú

Vật 1 có 12 ô, vật 2 có 3 ô và vật 3 có 5 ô. Hình dạng như hình phía trên.

Tác giả bài toán: Brian Dean, 2012