Hành trình của nhà vua

Lãnh thổ của vương quốc là một bảng hình chữ nhật kích thước $n\times m$. Thủ đô nằm ở ô góc trên bên trái $(1,1)$, ô góc dưới bên phải có toạ độ $(n,m)$.

Nhà vua muốn đi một vòng quanh vương quốc rồi quay về thủ đô: hành trình bắt đầu tại $(1,1)$, kết thúc tại $(1,1)$, và mỗi ô khác thủ đô được thăm đúng một lần, còn thủ đô được thăm đúng hai lần (lúc đầu và lúc cuối). Nhà vua chỉ có thể di chuyển sang ô kề cạnh.

Việc này không phải lúc nào cũng làm được, nên người ta cho phép xây thêm các cổng dịch chuyển một chiều. Mỗi ô được đặt nhiều nhất một cổng, mỗi cổng có một ô đích cố định và có thể dùng bao nhiêu lần tuỳ ý. Khi đứng trên ô có cổng, nhà vua tự chọn dùng hoặc không dùng cổng đó.

Hãy tìm số cổng dịch chuyển ít nhất cần xây để nhà vua hoàn thành hành trình, và chỉ ra một hành trình cụ thể.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $n$ và $m$ cách nhau bởi dấu cách.

Dữ liệu ra

Dòng đầu tiên in số nguyên $k$ là số cổng dịch chuyển ít nhất.

$k$ dòng tiếp theo, mỗi dòng bốn số nguyên $x_1{y}_1{x}_2{y}_2$ ($1\le x_1,x_2\le n$; $1\le y_1,y_2\le m$): cổng được đặt tại ô $(x_1,y_1)$ và dẫn tới ô $(x_2,y_2)$.

Sau đó in $n·m+1$ dòng, mỗi dòng hai số là toạ độ các ô theo đúng thứ tự nhà vua đi qua. Hành trình phải bắt đầu và kết thúc tại $(1,1)$.

Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

• $1\le n,m\le 100$
• $2\le n·m$

Ví dụ