Trò chơi xếp quân (Chips Puzzle)

Cho một bảng gồm $n$ hàng và $m$ cột. Mỗi ô của bảng chứa một xâu (có thể rỗng) gồm các ký tự '0' (quân trắng) và '1' (quân đen) xếp thành một hàng. Như vậy mỗi trạng thái của bảng được mô tả bằng một bảng các xâu nhị phân.

Bạn được phép thực hiện thao tác sau:

• Chọn hai ô khác nhau $(x_1,y_1)$ và $(x_2,y_2)$ nằm cùng một hàng hoặc cùng một cột, với điều kiện xâu tại ô $(x_1,y_1)$ không rỗng;
• Lấy ký tự cuối cùng của xâu tại ô $(x_1,y_1)$ và chuyển nó lên đầu xâu tại ô $(x_2,y_2)$.

Cho trạng thái đầu và trạng thái cuối của bảng. Đảm bảo rằng tổng số ký tự '0' và tổng số ký tự '1' ở hai trạng thái là như nhau. Gọi $s$ là tổng độ dài tất cả các xâu (giống nhau ở cả hai trạng thái). Hãy đưa ra một dãy thao tác biến trạng thái đầu thành trạng thái cuối, sao cho số thao tác không vượt quá $4·s$.

Có thể chứng minh rằng luôn tồn tại lời giải. Nếu có nhiều đáp án, in ra một đáp án bất kỳ thoả mãn.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số hàng và số cột của bảng.
• $n$ dòng tiếp theo mô tả trạng thái đầu: dòng thứ $i$ chứa $m$ xâu nhị phân không rỗng, xâu thứ $j$ là xâu ở ô $(i,j)$.
• $n$ dòng tiếp theo mô tả trạng thái cuối theo cùng định dạng.

Các hàng được đánh số từ $1$ đến $n$, các cột từ $1$ đến $m$.

Dữ liệu ra

• Dòng đầu in số nguyên $q$ — số thao tác sử dụng, với $0\le q\le 4·s$.
• $q$ dòng tiếp theo, mỗi dòng in bốn số nguyên $x_1,y_1,x_2,y_2$ mô tả một thao tác. Phải thoả mãn $1\le x_1,x_2\le n$, $1\le y_1,y_2\le m$, $(x_1,y_1)\ne (x_2,y_2)$, $x_1=x_2$ hoặc $y_1=y_2$, và tại thời điểm thực hiện, xâu ở ô $(x_1,y_1)$ phải khác rỗng.

Dãy thao tác này phải biến trạng thái đầu thành trạng thái cuối.

Ràng buộc

• $2\le n,m\le 300$
• $s\le 100000$ (tổng độ dài các xâu)
• Số lượng ký tự '0' và số lượng ký tự '1' trùng nhau ở hai trạng thái.

Ví dụ