Trò chơi ô chữ là một trong những trò chơi lâu đời nhất được con người phát minh ra. Ở trò chơi này, bạn được cho một bảng chữ nhật kích thước ~N \times M~ ~(N~ hàng ~M~ cột), được chia thành cách hình vuông nhỏ kích thước ~1 \times 1~. Ô ở hàng ~u~, cột ~v~ được ký hiệu là ô ~(u~, ~v)~. Có một số ô trống tạo thành các từ hàng ngang và hàng dọc. Bạn được cho một số gợi ý, và cần phải điền các chữ cái vào bảng dựa theo những gợi ý được cho.

Ở trong hình minh họa, bạn có một bảng kích thước ~15 \times 15~ ~(M = N = 15)~. Bạn cần điền những chữ cái vào các ô màu trắng. Chú ý rằng mỗi ô trắng thuộc ít nhất một từ hàng ngang hoặc một từ hàng dọc. Mỗi gợi ý có dạng:

• Từ hàng ngang bắt đầu từ ô đánh số ~1~ là tên ~1~ quốc gia
• Từ hàng dọc bắt đầu từ ô đánh số ~2~ là tên một thành phố
• ...

Một vài chú ý:

• Ô ~23~ là điểm bắt đầu của ~2~ từ: một từ nằm dọc, ~1~ từ nằm ngang. Trong bài này, một ô có thể là điểm bắt đầu của ~2~ từ ~(2~ từ đó phải có hướng khác nhau).
• Từ ngắn nhất bắt đầu từ ô ~1~, và có độ dài ~4~. Trong bài này, từ ngắn nhất hợp lệ có thể xuất hiện trên bảng cũng có độ dài là ~4~.

Trong bài toán này, nhiệm vụ của bạn là tạo ra một bảng ô chữ. Bạn được cho một bảng trống kích thước ~N \times M~ và một danh sách gồm ~K~ từ (các từ đôi một khác nhau). Nhiệm vụ của bạn là điền các từ này lên bảng sao cho:

• Mỗi từ được điền vào một dãy các ô liên tiếp theo chiều ngang từ trái sang phải hoặc chiều dọc từ trên xuống dưới.
• Các từ có cùng hướng với nhau và nằm trên cùng một hàng (hoặc cùng một cột) không được có ô chung hay chạm nhau ~(2~ ô được gọi là chạm nhau khi có chung một cạnh).
• Nếu một từ hàng ngang và một từ hàng dọc giao nhau, thì ô giao nhau phải có cùng chữ cái.
• Mỗi từ trong danh sách chỉ được điền đúng một lần lên bảng.

Input

• Dòng đầu tiên chứa ~3~ số tự nhiên ~N~, ~M~, ~K~. ~(1 \leq N~, ~M \leq 50~; ~1 \leq K \leq 1000)~
• ~K~ dòng tiếp theo, mỗi dòng chứa một từ ~(4 \leq~ độ dài từ ~\leq 30)~. Các từ chỉ gồm các chữ cái in thường từ ~a~ tới ~z~.

Output

• Dòng đầu tiên ghi ra một số tự nhiên ~X~ là số từ điền được vào bảng.
• ~X~ dòng sau, mỗi dòng ghi ~4~ số tự nhiên: id ~u~ ~v~ ~t~ với ý nghĩa: từ thứ id được điền vào vị trí ~(u~, ~v)~ trên bảng. Nếu ~t = 0~ thì từ được điền từ trái sang phải, nếu ~t = 1~ thì từ được điền từ trên xuống dưới. Chú ý rằng các từ của bạn phải được điền hoàn toàn vào bên trong bảng (không chữ cái nào được điền ra ngoài bảng).

Giới hạn

• Với mỗi test, nếu output của bạn không hợp lệ, bạn được ~0~ điểm. Nếu output hợp lệ:

  • Gọi ~X~ là số từ nằm ngang mà bạn điền được lên bảng.
  • Gọi ~Y~ là số từ nằm dọc mà bạn điền được lên bảng.
  • Gọi ~Z~ là số ô thuộc ~2~ từ ~(1~ từ nằm ngang và ~1~ từ nằm dọc).
  • Gọi ~T~ là số ô thuộc ít nhất ~1~ từ.
  • Điểm của bạn là: $$\min\left(20, \frac{X \times Y + Z^{1.5} + T}{M \times N} \right)$$.

Sample Input

4 4 4
abcd
xyzt
buyv
dwtz

Sample Output

4
1 1 1 0
2 3 1 0
3 1 2 1
4 1 4 1

Note

Với output này:

• ~X = 2~
• ~Y = 2~
• ~Z = 4~
• ~T = 12~