Thành phố Tablecity

Thành phố Tablecity là một lưới $1000\times 2$, mỗi ô là một khu phố mang tên $(X,Y)$ với $1\le X\le 1000$ và $1\le Y\le 2$.

Có một tên trộm đang lẩn trốn trong thành phố. Ở thời điểm ban đầu (giờ thứ $1$), tên trộm có thể ở bất kỳ ô nào trong lưới. Mỗi giờ trôi qua, sau khi cảnh sát điều tra xong, tên trộm sẽ rời khu phố $(X,Y)$ hiện tại và di chuyển sang đúng một trong các khu phố sau (miễn là khu phố đó nằm trong thành phố):

$$(X-1,Y),(X+1,Y),(X-1,Y-1),(X-1,Y+1),(X+1,Y-1),(X+1,Y+1).$$

Nói cách khác, hoành độ $X$ luôn đổi $\pm 1$, còn tung độ $Y$ có thể đổi $-1$, $0$ hoặc $+1$.

Cảnh sát trưởng Albert có đủ người để mỗi giờ kiểm tra đúng hai khu phố. Nếu trong giờ đó tên trộm đang ở một trong hai khu phố bị kiểm tra thì hắn bị bắt.

Albert đã hứa với Tổng thống rằng sẽ bắt được tên trộm trong không quá $2015$ giờ. Hãy giúp Albert lập kế hoạch điều tra đảm bảo bắt được tên trộm, bất kể vị trí ban đầu và chiến lược di chuyển của hắn.

Dữ liệu vào

Không có dữ liệu vào.

Dữ liệu ra

Dòng đầu in số nguyên $N$ — số giờ cảnh sát điều tra ($0\le N\le 2015$).

Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa $4$ số nguyên $X_{i,1}{Y}_{i,1}{X}_{i,2}{Y}_{i,2}$ là toạ độ hai khu phố mà cảnh sát kiểm tra trong giờ thứ $i$ (theo thứ tự thời gian). Cần đảm bảo $1\le X\le 1000$ và $1\le Y\le 2$.

Kế hoạch của bạn phải đảm bảo: với mọi vị trí ban đầu của tên trộm và mọi cách di chuyển hợp lệ của hắn, tên trộm sẽ bị bắt trong vòng $N$ giờ.

Bài có nhiều đáp án hợp lệ. Bộ chấm sẽ mô phỏng tên trộm theo hướng bất lợi nhất để xác nhận kế hoạch của bạn có đảm bảo bắt được hay không.

Ràng buộc

• $0\le N\le 2015$
• $1\le X\le 1000$, $1\le Y\le 2$ cho mọi toạ độ kiểm tra.

Ví dụ