Bài toán con mã đi tuần là bài toán nổi tiếng. Một con mã đặt vào một vị trí trên bàn cờ quốc tế cỡ \(n*n\) nó rất thông minh tìm ra một cách nhảy đi hết bàn cờ mỗi ô nó chỉ đặt chân lên đúng 1 lần

Bạn đã biết cách đi của nó bạn hãy chỉ ra cách nhẩy của nó

Input

Dòng đầu là số nguyên dương n là kích cỡ của bàn cờ có giá trị không vượt quá 10

Tiếp theo là ma trận cỡ \(n*n\) là cách nhảy của nó

Output

Bạn xuất ra màn hình lần lượt tọa độ mà nó đã nhảy

Ví dụ

Input

8
 15  8  5  2 13 10 19 22
  6  3 14  9 18 21 34 11
 29 16  7  4  1 12 23 20
 26 37 28 17 24 35 42 33
 53 30 25 36 41 32 49 60
 38 27 54 31 50 59 46 43
 55 52 63 40 57 44 61 48
 64 39 56 51 62 47 58 45

Output

(3,5) (1,4) (2,2) (3,4) (1,3) (2,1) (3,3) (1,2) (2,4) (1,6) (2,8) (3,6) (1,5) (2,3) (1,1) (3,2) 
(4,4) (2,5) (1,7) (3,8) (2,6) (1,8) (3,7) (4,5) (5,3) (4,1) (6,2) (4,3) (3,1) (5,2) (6,4) (5,6)
(4,8) (2,7) (4,6) (5,4) (4,2) (6,1) (8,2) (7,4) (5,5) (4,7) (6,8) (7,6) (8,8) (6,7) (8,6) (7,8) 
(5,7) (6,5) (8,4) (7,2) (5,1) (6,3) (7,1) (8,3) (7,5) (8,7) (6,6) (5,8) (7,7) (8,5) (7,3) (8,1)