Cho 2 con Mã trên bàn cờ quốc tế N*N được đánh chỉ số các ô theo hàng và cột đều từ \(1\) đến \(N\), và một vị trí đích trên bàn cờ đó, hỏi con nào đến được trước

Yêu cầu: Quân mã đi theo đúng bước nhảy của quân mã trên bàn cờ quốc tế và không được nhảy ra ngoài bàn cờ, mỗi bước đi chỉ thực hiện một lần nhẩy

Input

Dòng đầu chứa kích thước của bàn cờ \(N\) \((1 \le N \le 100)\)

Dòng thứ 2 tọa độ của con mã thứ nhất \((x1,y1)\) thỏa mãn \(1 \le x1,y1 \le N\)

Dòng thứ 3 tọa độ của con mã thứ hai \((x2,u2)\) thỏa mãn \(1 \le x2,y2 \le N\)

Dòng cuối chứa tọa độ đích \((u,v)\) thỏa mãn \(1 \le u,v \le N\)

Output

Dòng đầu con nào số bước nhảy ít hơn hoặc nó đến được mà con kia không đến được đích thì con đó thắng xuất ra số 1 hoặc 2 tùy theo con thắng, trong trường hợp 2 con đến bằng nhau hoặc cùng không có cách nào đến được đích xuất ra 0

Dòng thứ 2 xuất ra hai số nguyên là số bước ngắn nhất của con mã 2 nhảy tới đích, con nào không đến được đích xuất \(-1\)

Ví dụ 1

Input

6
1 1 
1 2
6 6

Output

2
4 3

Ví dụ 2

Input

7
1 1 
1 7
7 4

Output

0
3 3