Truyền màn chơi tiết kiệm

Khi tải dữ liệu của một trò chơi, bạn cần nhận mô tả của $k$ màn chơi từ máy chủ. Mỗi mô tả là một bản đồ dạng lưới ô vuông kích thước $n\times m$. Một số ô của bản đồ chứa kẹo (mỗi ô chứa nhiều nhất một viên). Ô trống được ký hiệu bởi dấu chấm ., còn ô chứa kẹo được ký hiệu bởi một chữ cái Latinh (chữ hoa và chữ thường được phân biệt). Các viên kẹo giống nhau ở các màn chơi khác nhau có thể được biểu diễn bằng cùng một chữ cái.

Khi truyền dữ liệu qua mạng, bạn muốn giảm tổng số byte phải truyền. Các màn chơi có thể được truyền theo thứ tự bất kỳ. Với mỗi màn chơi $A$, có hai cách truyền:

1. Truyền toàn bộ màn chơi $A$ — tốn $n·m$ byte.
2. Nếu đã có một màn chơi $B$ được truyền trước đó, có thể truyền hiệu giữa $A$ và $B$ — tốn $d_{A,B}·w$ byte, trong đó $d_{A,B}$ là số ô khác nhau giữa $A$ và $B$ (so sánh từng cặp ô tương ứng — không xoay, không dịch chuyển bản đồ), còn $w$ là một hằng số cho trước.

Hãy tìm cách truyền cả $k$ màn chơi sao cho tổng số byte truyền là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $m$, $k$, $w$.
• Tiếp theo là mô tả của $k$ màn chơi. Mỗi màn chơi gồm $n$ dòng, mỗi dòng gồm $m$ ký tự (chữ cái Latinh hoa/thường, hoặc dấu .). Các màn chơi được đánh số từ $1$ đến $k$ theo thứ tự xuất hiện trong dữ liệu vào.

Dữ liệu ra

• Dòng đầu in tổng số byte nhỏ nhất phải truyền.
• $k$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $x_i$ và $y_i$, mô tả thứ tự truyền: màn chơi thứ $x_i$ được truyền ở bước $i$ theo cách $y_i$. Nếu $y_i=0$ thì truyền toàn bộ; ngược lại $y_i$ là số hiệu của một màn chơi đã được truyền trước đó và ta truyền hiệu giữa màn $y_i$ và màn $x_i$.

Nếu có nhiều phương án tối ưu, in ra phương án bất kỳ.

Ràng buộc

• $1\le n,m\le 10$
• $1\le k,w\le 1000$

Ví dụ