Cho bàn cờ vua (cờ quốc tế) kích thước n x n. Tìm số bước đi ít nhất để một quân mã xuất phát ở ô (x1, y1) đi đến ô (x2, y2).

Dòng đầu là số nguyên dương n ( 6 ≤ n ≤ 1000)

Dòng thứ 2 chứa 4 số nguyên x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n)

Ghi ra:

Dòng đầu là số bước đi ít nhất.

Các dòng tiếp theo: mỗi dòng ghi các ô đi qua, bắt đầu từ (x1, y1).

Ví dụ:

Input

8
2 3 3 3

Output

3
2 3
4 4
2 5
3 3