Giải bài trực tuyến

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*M (N hàng M cột), được chia thành cách hình vuông nhỏ kích thước 1*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*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*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 ≤ N, M ≤ 50; 1 ≤ K ≤ 1000)

K dòng tiếp theo, mỗi dòng chứa một từ (4 ≤ độ dài từ ≤ 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).

Cách tính điểm

• 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à (X * Y + Z^1.5 + T) / (M * N).
• Vì đây là bài challenge, nên điểm chung cuộc của bạn trong kỳ thi VM14 được tính theo công thức:
  • Giả sử bạn đứng thứ i trong bảng xếp hạng của bài (nghĩa là có i-1 người điểm cao hơn bạn).
  • Điểm mà bạn nhận được là
    
    với log là log cơ số e.
• Bài này gồm 20 test. Trong quá trình thi, bài của bạn sẽ được chấm với 10 test.

Example

Input:
4 4 4

abcd

xyzt

buyv

dwtz

Output:
4

1 1 1 0

2 3 1 0

3 1 2 1

4 1 4 1

Với output này:

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