Có thể bạn chưa biết, ngoài trà sữa, GSPVH còn có một đặc sản khác đó chính là boardgame. Nếu như trà sữa được GSPVH phát cho tất cả các bạn học trên lớp, thì những bữa tiệc boardgame sẽ được tổ chức vào buổi tối. Boardgame là hình thức giải trí vui vẻ, hấp dẫn và vô cùng lành mạnh. Khi đắm chìm trong những bữa tiệc boardgame, chúng ta sẽ xích lại gần hơn với những người bạn của mình, thay thế tương tác ảo trên mạng xã hội bởi phút giây cuộc trò chuyện thực tế, và không lo bị tốn thời gian vào những trò chơi vô bổ như Genshin hay Liên Quân. Hơn thế nữa, boardgame còn làm tăng khả năng tư duy thuật toán và lý thuyết trò chơi, điều rất quan trọng với các bạn chuẩn bị thi học sinh giỏi quốc gia.

Trong chuyến đi dạy lần này, để đổi món, GSPVH đã tạo ra một trò boardgame mới để thử thách các bạn học sinh.

GSPVH vẽ trên nền nhà một lưới ô vuông gồm \(m\) hàng và \(n\) cột. Các hàng được đánh số từ \(1\) đến \(m\), các cột được đánh số từ \(1\) đến \(n\). Ô ở hàng \(i\) và cột \(j\) được ký hiệu là \((i, j)\). Trên mỗi ô của lưới, GSPVH có ghi một ký tự. GSPVH mời \(q\) bạn lần lượt tham gia trò chơi. GSPVH phát cho mỗi bạn một xâu ký tự, bạn thứ \(i\) nhận được xâu \(s_i\). Sau đó, các bạn lần lượt thực hiện phần chơi "di chuyển trên lưới". Luật chơi như sau:

• Người chơi được phép xuất phát ở một ô bất kỳ trên lưới và kết thúc ở một ô bất kỳ trên lưới.
• Tại mỗi bước, người chơi đi từ ô hiện tại sang một ô kề cạnh.
• Người chơi không được đi ra ngoài bảng.
• Người chơi không được quay lại ô mà mình vừa tới ở bước liền trước đó. Nói cách khác, nếu người chơi thực hiện hai bước di chuyển liên tiếp là từ ô \((x_1, y_1)\) sang ô \((x_2, y_2)\) và từ ô \((x_2, y_2)\) sang ô \((x_3, y_3)\); thì hai ô \((x_1, y_1)\) và \((x_3, y_3)\) phải khác nhau.
• Trong quá trình di chuyển, người chơi có thể đi qua một ô nhiều lần.
• Xét xâu ký tự \(t\) được xây dựng như sau:
  • Ban đầu xâu \(t\) chỉ chứa một ký tự là ký tự được ghi ở ô người chơi chọn làm ô xuất phát.
  • Sau mỗi bước đi, người chơi thêm vào cuối xâu \(t\) một ký tự là ký tự được ghi ở ô người đó vừa đi tới.
• Kết thúc quá trình di chuyển, xâu \(t\) nói trên phải là một xâu bội của xâu mà người chơi nhận được từ GSPVH.

Xâu ký tự \(\alpha\) được gọi là xâu bội của xâu ký tự \(\beta\) khi và chỉ khi tồn tại số nguyên dương \(\kappa\) sao cho \(\alpha\) bằng \(\kappa\) xâu \(\beta\) ghép lại với nhau. Ví dụ, gspvh, gspvhgspvh, gspvhgspvhgspvh đều là các xâu bội của gspvh, nhưng pvhgs hay pvhgspvh thì không.

GSPVH tuyên bố, nếu phần chơi của các bạn càng kéo dài (tức độ dài xâu \(t\) theo mô tả ở trên càng lớn) thì GSPVH càng tặng nhiều trà sữa. Vì vậy, các bạn đều muốn số bước di chuyển mình thực hiện được là lớn nhất. Tuy nhiên, để tránh bị kiệt sức do nhảy quá nhiều, các bạn cũng muốn biết liệu số bước tối đa có lớn quá hay không.

Dữ liệu

Vào từ file văn bản boardgame.inp:

• Dòng đầu tiên chứa một số nguyên \(\tau\) là số bộ dữ liệu.
• Tiếp theo là các bộ dữ liệu, mỗi bộ được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa ba số nguyên dương \(m, n\) và \(q\) \((1 \leq m \cdot n \leq 2 \cdot 10^5, 1 \leq q \leq 10)\).
  • Trong \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) ký tự mô tả lưới ô vuông.
  • Dòng cuối cùng chứa \(q\) xâu ký tự \(s_1, s_2, \ldots, s_q\). Tất cả các xâu đều khác rỗng và thỏa mãn tính chất: các ký tự trong xâu đôi một phân biệt.

Gọi:

• \(\Sigma_{m \cdot n}\) là tổng giá trị \(m \cdot n\) trong tất cả các bộ dữ liệu trong một test.
• \(\Sigma_{q}\) là tổng giá trị của \(q\) trong tất cả các bộ dữ liệu trong một test.
• \(\Sigma_{s}\) là tổng độ dài các xâu \(s_1, s_2, \ldots, s_q\) trong tất cả các bộ dữ liệu trong một test.

Dữ liệu đảm bảo:

• Lưới ô vuông và các xâu \(s_1, s_2, \ldots, s_q\) chỉ chứa các chữ cái in hoa, chữ cái in thường, chữ số và các ký tự !, @, #, $, %, ^, &, *.
• \(\Sigma_{m \cdot n} \leq 10^6\)
• \(\Sigma_{s} \leq 10^6\)

Kết quả

Ghi ra file văn bản boardgame.out:
- Với mỗi bộ dữ liệu, in ra \(q\) số nguyên trên một dòng. Số thứ \(i\) là giá trị lớn nhất của độ dài xâu \(t\) (trong phần mô phỏng luật chơi) mà bạn thứ \(i\) có thể tạo ra, hoặc \(-1\) nếu tồn tại cách để người chơi này đi nhiều hơn \(2207^{1997}\) bước.

Ràng buộc

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(25\) điểm): \(m \cdot n < m + n\)
• Subtask \(2\) (\(20\) điểm): Các xâu \(s_1, s_2, \ldots, s_q\) có độ dài nhỏ hơn \(3\).
• Subtask \(3\) (\(25\) điểm): \(m \cdot n \le 8 \cdot 10^3\) và \(\Sigma_{m \cdot n} \leq 4 \cdot 10^4\).
• Subtask \(4\) (\(30\) điểm): Không có ràng buộc gì thêm.

Với mỗi test, nếu file kết quả của bạn không đúng format (chứa ký tự lạ, chứa nhiều hơn hoặc ít hơn \(\Sigma_{q}\) số nguyên,...), bạn sẽ được \(0\) điểm. Ngược lại, gọi \(\rho\) là số giá trị khớp với đáp án của giám khảo, số điểm bạn nhận được là \((\frac{\rho}{\Sigma_{q}})^{\sqrt{2.27}}\). Điểm tối đa của một test là \(1\).

Ví dụ

2

4 4 2
abca
abab
cabc
abba
abc bc

5 5 3
LQDQd
QDOLJ
LOJLO
QDIQD
LOjLO
LQDOJ DOJI LQD

6 2
-1 -1 3