To read the problem statement in English, choose the language using the flag on the navigation bar.

Cờ vua là một loại trò chơi cờ với hai người chơi, và cũng là loại cờ nổi tiếng nhât thế giới. Bé Mèo rất muốn học chơi cờ, nhưng trong cờ vua có đến $6$ loại quân khác nhau, mỗi loại lại có một cách di chuyển khác nhau, nên Bé Mèo cảm thấy rất bối rối! Vì vậy hôm nay chúng ta giúp Bé Mèo làm quen với quân tượng, nhưng với một bàn cờ vua có kích thước là $n\times n$ bất kì.

Một bàn cơ vua có kích thước $n\times n$ là bàn cờ vua gồm có $n$ hàng và $n$ cột. Các hàng được đánh số từ $1$ đến $n$ từ trên xuống, và các cột được đánh số từ $1$ đến $n$ từ trái qua phải. Ô ở hàng thứ $r$ và cột thứ $c$ được biểu diễn bởi cặp số $(r,c)$.

Ta có thể di chuyển quân tượng theo đường chéo trên bàn cờ. Cụ thể, nếu như có một quân tượng tại vị trí $(i,j)$, ta có thể di chuyển quân tượng đến ô $(i^{\prime },j^{\prime })$ thỏa mãn $|i-i^{\prime }|=|j-j^{\prime }|$.

Minh họa cho các nước đi của quân tượng tại vị trí $(4,4)$. Các ô màu vàng là các ô mà quân tượng này có thể đến được

Để làm quen với cách di chuyển quân tượng, Bé Mèo cần thực hiện bài tập sau. Trên bàn cờ của chúng ta hiện tại có duy nhất một quân tượng tại vị trí $(i,j)$. Hãy kiểm tra xem ta có thể di chuyển quân tượng đến ô $(x,y)$ bằng một vài nước di chuyển (có thê không cần di chuyển) hay không. Nếu có thể, hãy tìm một cách đi từ ô $(i,j)$ đến ô $(x,y))$ với số lượng nước di chuyển cần thực hiện là ít nhất có thể. Để thành thạo, nên Bé Mèo cần luyện tập bài tập này $q$ lần. Nhưng Bé Mèo vẫn đang rất mải chơi, nên không chịu tập chung luyện tập, nên bạn hãy giúp Bé Mèo thực hiện bài tập này nhé!

Input

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1\le n\le {10}^9$, $1\le q\le {10}^5$) lần lượt là số hàng của bàn cờ vua, số cột của bàn cờ vua, và số lượng bài tập bạn cần thực hiện.

Mỗi dòng trong $q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $i$, $j$, $x$ và $y$ ($1\le i,j,x,y\le n$), với $(i,j)$ thể hiện vị trí của quân tượng, và $(x,y)$ là vị trí cần di chuyển quân tượng đến trong bài tập.

Output

Với mỗi bài tập, nếu không có cách nào di chuyển quân tượng từ ô $(i,j)$ đến ô $(x,y)$, hãy in ra $-1$.

Ngược lại, hãy in ra số $s$ là số lượng nước di chuyển ít nhất cần thực hiện để di chuyển quân tượng từ. Sau đó, hãy in ra $s$ dòng. Trên dòng thứ $t$, hãy in ra hai số nguyên $r$ và $c$ là ô cần di chuyển tới trong nước di chuyển thứ $t$.

Nếu có nhiều cách di chuyển quân tượng đến đích, hãy in ra cách di chuyển bất kì.

Scoring

• Subtask 1, tương ứng với $15$ điểm, có $n\le 2$.

• Subtask 2, tương ứng với $15$ điểm, có $n\le 8$.

• Subtask 3, tương ứng với $20$ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán có $50$ điểm.

Sample Input 1

2 4
1 1 1 1
1 1 2 2
2 1 2 2
1 2 2 1

Sample Output 1

0
1
2 2
-1
1
2 1

Sample Input 2

3 5
1 1 3 3
2 1 2 3
1 2 3 2
2 2 1 1
2 2 1 2

Sample Output 2

1
3 3
2
1 2
2 3
2
2 1
3 2
1
1 1
-1

Notes

Trong bài tập cuối của ở ví dụ đầu tiên, Bé Mèo có thể di chuyển quân tượng với một nước đi như sau:

Trong bài tập đều tiên ở ví dụ thứ hai, Bé Mèo có thể di chuyển quân tượng trong một nước đi như sau:

Trong bài tập thứ hai ở ví dụ thứ hai, Bé Mèo có thể di chuyển quân tượng trong hai nước đi như sau. Lưu ý rằng trong bài tập này cũng có thể di chuyển quân tượng đến ô $(3,2)$ trước rồi mới di chuyển quân tượng đến đích.