Máy bay là phương tiện di chuyển hiện đại nhất của loài người. Kể từ khi những chú chim sắt xuất hiện trên bầu trời cao, thời gian để chúng ta đi từ Á sang Âu, từ Âu sang Mỹ, từ Mỹ sang Phi chỉ còn tính bằng giờ. Vượt lên trên vai trò giúp con người đi lại, máy bay còn gắn liền với dịch vụ sang chảnh và hình ảnh của một đất nước. Đi máy bay, bạn không chỉ được du ngoạn khắp năm châu, mà còn được thưởng thức những bữa ăn ngon, xem những bộ phim kinh điển và chìm đắm trong những trải nghiệm mà chỉ trên 9 tầng mây mới có. Những sân bay quốc tế --- cửa ngõ chào đón bạn bè năm châu, luôn được đầu tư xây dựng sang xịn mịn để đem lại cho du khách những ấn tượng khó phai ngay trong giây phút đầu tiên đặt chân tới một quốc gia.

Tuy nhiên, khác với ô tô hay xe lửa, máy bay không thể dừng đỗ ở một nơi bất kì mà chỉ có thể xuất phát và kết thúc hành trình ở những sân bay được xây dựng sẵn. Bởi thế, dù máy bay là để kết nối khắp nơi trên Trái Đất, việc đi từ một thành phố tới một thành phố khác thường cần nhiều hơn một chuyến bay. Chẳng hạn, để đi từ Hà Nội tới Zurich (Thụy Sỹ), bạn cần thực hiện hai chuyến bay từ Hà Nội đi Paris và từ Paris đi Zurich do không có chuyến bay thẳng từ Hà Nội đi Zurich. Có những hành trình khác còn gian nan hơn nhiều, chẳng hạn chặng đường từ Buôn Mê Thuột đi South Dakota (Hoa Kỳ) sẽ bao gồm 4 chuyến bay Buôn Mê Thuột -> Hà Nội -> Tokyo -> Dallas -> South Dakota. Việc đi nhiều chuyến bay trong một hành trình gọi là nối chuyến (flight connection hay transit). Trong phần đa các trường hợp, nối chuyến là bắt buộc do không có chuyến bay trực tiếp kết nối nơi bạn xuất phát và nơi bạn muốn tới. Nhưng cũng có trường hợp khác, dù có chuyến bay thẳng, nhưng người ta vẫn chọn nối chuyến bay, nhằm tránh phải ngồi liên tục trên máy bay trong thời gian dài và được khám phá thêm nhiều sân bay đẹp trên thế giới. Chẳng hạn, để đi từ Singapore tới San Francisco, thay vì bay chuyến bay thẳng kéo dài 17 tiếng, hành khách sẽ bay hai chuyến từ Singapore đi TP. Hồ Chí Minh và từ TP. Hồ Chí Minh đi San Francisco, để có thể được khám phá thêm một sân bay đẹp.

Một hãng hàng không nọ có mạng bay kết nối ~n~ sân bay. Các sân bay này được đánh số từ ~1~ đến ~n~. Hãng cung cấp chuyến bay thẳng không dừng giữa hai sân bay bất kì trong số ~n~ sân bay này. Cụ thể, chuyến bay một chiều của hãng khởi hành từ sân bay ~i~ và hạ cánh ở sân bay ~j~ có thời gian bay là ~t_{i, j}~. Trong ~n~ sân bay này, hãng hàng không giới thiệu ~m~ sân bay có nhiều cảnh đẹp hấp dẫn và kiến trúc độc đáo mà hành khách nên ghé thăm ít nhất một lần. Đó là các sân bay ~f_1, f_2, \ldots, f_m~.

Sắp tới đây, GS. PVH có ~q~ kế hoạch di chuyển. Trong kế hoạch thứ ~k~, GS. PVH cần đi từ sân bay ~o_k~ đến sân bay ~d_k~. Là một fan cứng của máy bay và các trải nghiệm hàng không, GS. PVH muốn rằng trong mỗi kế hoạch di chuyển, GS. PVH sẽ đi từ sân bay xuất phát, qua ~m~ sân bay có cảnh đẹp hấp dẫn kể trên mỗi sân bay ít nhất một lần trước khi hạ cánh ở sân bay đích. GS. PVH không ngại phải lên xuống máy bay nhiều lần, nên GS. PVH không cần cực tiểu hóa số chuyến bay trên hành trình. Tuy nhiên, vì lý do công việc, GS. PVH muốn tổng thời gian bay của các chuyến bay trên hành trình là nhỏ nhất.

Các bạn hãy giúp GS. PVH với mỗi kế hoạch di chuyển của mình, thiết kế một hành trình bay từ sân bay xuất phát, ghé thăm mỗi sân bay có cảnh đẹp hấp dẫn ít nhất một lần rồi dừng lại ở sân bay đích, với tổng thời gian bay nhỏ nhất.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~q~ ~(1 \leq n \leq 1500, 1 \leq m \leq 17, 1 \leq q \leq 190000)~; lần lượt là số sân bay trong mạng bay của hãng hàng không, số sân bay hấp dẫn cần phải ghé qua và số kế hoạch di chuyển của GS. PVH.

Dòng thứ hai chứa ~m~ số nguyên phân biệt ~f_1, f_2, \ldots, f_m~ ~(1 \leq f_i \leq n)~ thể hiện ~m~ sân bay hấp dẫn mà hành khách nên ghé qua.

Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên ~d_{i, 1}, d_{i, 2}, \ldots, d_{i, n}~ ~(0 \leq d_{i, j} \leq 999)~ trong đó ~d_{i, j}~ là thời gian bay của chuyến bay từ sân bay ~i~ đến sân bay ~j~. Dữ liệu vào đảm bảo ~d_{i, j} = 0~ khi và chỉ khi ~i = j~.

Trong ~q~ dòng cuối cùng, dòng thứ ~k~ chứa hai số nguyên ~o_k, d_k~ ~(1 \leq o_k, d_k \leq n)~ lần lượt là sân bay xuất phát và sân bay kết thúc trong kế hoạch di chuyển thứ ~k~ của GS. PVH.

Output

In ra ~q~ số nguyên trên một dòng, số nguyên thứ ~k~ là tổng thời gian bay nhỏ nhất của hành trình bay cho kế hoạch di chuyển thứ ~k~.

Sắp tát

Bộ test của bài được chia làm các sắp tát như sau:

• Sắp tát ~1~ (~7~ điểm): ~d_{i, j} = 1~ với mọi ~1 \leq i, j \leq n~ và ~i \neq j~.
• Sắp tát ~2~ (~10.5~ điểm): ~m = 1~
• Sắp tát ~3~ (~10.5~ điểm): ~m \leq 3~
• Sắp tát ~4~ (~10.5~ điểm): ~m \leq 6~
• Sắp tát ~5~ (~14~ điểm): ~n \leq 500~
• Sắp tát ~6~ (~17.5~ điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~70~ điểm.

Ví dụ

Input

6 3 4
1 3 5 
0 9 11 8 10 15 
9 0 6 1 5 10 
11 6 0 7 1 4 
8 1 7 0 6 11 
10 5 1 6 0 5 
15 10 4 11 5 0 
1 6
2 5
6 2
2 4

Output

15 21 24 25

Giải thích

Trong ví dụ ở trên, có ~n = 6~ sân bay; trong số đó các sân bay ~1~, ~3~, ~5~ là những sân bay hấp dẫn mà GS. PVH muốn đi qua trong bất kì hành trình nào của mình.

• Với kế hoạch di chuyển thứ nhất, từ sân bay ~1~ đến sân bay ~6~, GS. PVH nên chọn hành trình bay ~1 \rightarrow 5 \rightarrow 3 \rightarrow 6~ với tổng thời gian bay là ~d_{1, 5} + d_{5, 3} + d_{3, 6} = 10 + 1 + 4 = 15~.
• Với kế hoạch di chuyển thứ hai, từ sân bay ~2~ đến sân bay ~5~, GS. PVH nên chọn hành trình bay ~2 \rightarrow 1 \rightarrow 3 \rightarrow 5~ với tổng thời gian bay là ~d_{2, 1} + d_{1, 3} + d_{3, 5} = 9 + 11 + 1 = 21~.
• Với kế hoạch di chuyển thứ ba, từ sân bay ~6~ đến sân bay ~2~, GS. PVH nên chọn hành trình bay ~6 \rightarrow 3 \rightarrow 5 \rightarrow 1 \rightarrow 2~ với tổng thời gian bay là ~d_{6, 3} + d_{3, 5} + d_{5, 1} + d_{1, 2} = 4 + 1 + 10 + 9 = 24~.

Xét hai xâu kí tự bất kì ~a = a_1 a_2 \ldots a_m~ và ~b = b_1 b_2 \ldots b_n~. Ta nói độ dài tiền tố chung dài nhất của hai xâu ~a~ và ~b~ là ~l~ khi và chỉ khi:

• ~l \leq m~ và ~l \leq n~.
• Với mọi ~1 \leq i \leq l~, ta có ~a_i = b_i~.
• ~l~ là số nguyên lớn nhất sao cho cả hai điều trên đều đúng.

Ví dụ, độ dài tiền tố chung dài nhất của hai xâu "gsts" và "gspvh" là ~2~, độ dài tiền tố chung dài nhất của hai xâu "iloveyou" và "iloveyoubabe" là ~8~, độ dài tiền tố chung dài nhất của hai xâu "com" và "tro" là ~0~.

Cho ~n~ xâu kí tự ~s_1, s_2, \ldots, s_n~ và một số nguyên ~k~. Bạn cần chọn ra ~k~ xâu trong số ~n~ xâu trên sao cho tổng độ dài tiền tố chung dài nhất của mọi cặp hai xâu được chọn là lớn nhất có thể. Nói cách khác, giả sử các xâu được chọn là ~x_1, x_2, \ldots, x_k~ và gọi ~lcp(u, v)~ là độ dài tiền tố chung dài nhất của hai xâu ~s_u~ và ~s_v~, bạn cần cực đại hóa giá trị sau: ~\sum_{i = 1}^{k} \sum_{j = i + 1}^{k} lcp(x_i, x_j)~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \leq k \leq n \leq 5000)~.

Trong ~n~ dòng còn lại, dòng thứ ~i~ chứa xâu kí tự ~s_i~. Xâu kí tự này khác rỗng và chỉ gồm các chữ cái in thường.

Dữ liệu vào đảm bảo tổng độ dài của các xâu ~s_1, s_2, \ldots, s_n~ không quá ~4 \cdot 10^6~.

Output

In ra một số nguyên duy nhất là giá trị lớn nhất của biểu thức ở trên, là tổng của độ dài tiền tố chung dài nhất xét trên mọi cặp xâu kí tự được chọn.

Sắp tát

Bộ test của bài được chia làm các sắp tát như sau:

• Sắp tát ~1~ (~10~ điểm): Tất cả các xâu chỉ gồm một loại ký tự. Cụ thể, các xâu ~s_i~ chỉ có thể là "a", "bb", hay "ccc" mà không thể là "ab" hay "cac".
• Sắp tát ~2~ (~10~ điểm): ~k = n~
• Sắp tát ~3~ (~10~ điểm): ~k = 3~
• Sắp tát ~4~ (~10~ điểm): ~n \leq 20~
• Sắp tát ~5~ (~15~ điểm): ~n \leq 500~ và độ dài mỗi xâu không quá ~500~.
• Sắp tát ~6~ (~15~ điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~70~ điểm.

Ví dụ

Input 1

7 3
diduduadi
duadidudi
dudua
dudu
didi
didudua
duadidu

Output 1

13

Input 2

5 3
pvhoi
tigersugar
gspvh
ndt
fos

Output 2

0

Giải thích

Trong ví dụ đầu tiên, phương án tối ưu là chọn ba xâu ~s_1~, ~s_5~ và ~s_6~. Khi đó:

• ~lcp(1, 5) = 3~
• ~lcp(1, 6) = 7~
• ~lcp(5, 6) = 3~

Tổng độ dài tiền tố chung dài nhát của các cặp xâu được chọn là ~3 + 7 + 3 = 13~

Trong ví dụ thứ hai, hai xâu bất kì trong các xâu đã cho đều có độ dài tiền tố chung dài nhất bằng ~0~. Vì vậy, mọi cách chọn ~k~ xâu đều cho ra tổng độ dài tiền tố chung dài nhất là ~0~.

Cho một bảng gồm ~m~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~m~ theo thứ tự từ trên xuống dưới và các cột được đánh số từ ~1~ đến ~n~ theo thứ tự từ trái qua phải. Ô ở hàng ~i~ và cột ~j~ được kí hiệu là ~(i, j)~. Trên mỗi ô của bảng có ghi một chữ số từ ~0~ đến ~9~.

Một đường đi hợp lệ trên bảng này là một đường đi xuất phát từ ô góc trái trên và kết thúc ở ô góc phải dưới, đồng thời mỗi bước đi chỉ đi xuống ô ngay phía dưới hoặc ngay bên phải. Nói cách khác, một đường đi hợp lệ là một dãy các ô thỏa mãn:

• Ô đầu tiên là ~(1, 1)~.
• Ô cuối cùng là ~(m, n)~.
• Kế tiếp sau ô ~(i, j)~ là ô ~(i, j + 1)~ hoặc ô ~(i + 1, j)~.

Xét bảng số dưới đây với ~m = 3~ hàng và ~n = 4~ cột:

~1~ ~2~ ~3~ ~4~

~5~ ~6~ ~7~ ~8~

~9~ ~0~ ~3~ ~6~

Ta tiến hành liệt kê mọi đường đi hợp lệ trên bảng này. Với mỗi đường đi, ta lần lượt viết các chữ số ở các ô đi qua để tạo thành một con số. Khi đó, ta sẽ được các số sau: ~123486~, ~123786~, ~123736~, ~126786~, ~126736~, ~126036~, ~156786~, ~156736~, ~156036~ và ~159036~.

Một bảng chữ số được gọi là hoàn toàn chia hết cho ~p~ khi và chỉ khi tất cả các con số tạo được từ mọi đường đi hợp lệ đều chia hết cho ~p~. Ví dụ, bảng số dưới đây

~3~ ~4~ ~5~

~7~ ~2~ ~6~

hoàn toàn chia hết cho ~3~ vì mọi số tạo thành từ mọi đường đi hợp lệ đều chia hết cho ~3~.

Cho một bảng chữ số, bạn được biến đổi bảng chữ số thông qua thao tác sau: Ở mỗi lần biến đổi, bạn chọn ra một ô ~(i, j)~ trên bảng và thay đổi chữ số tại ô này theo một trong những cách sau:

• Nếu hiện tại ô đang chứa chữ số ~d > 0~, bạn được đổi sang chữ số ~d - 1~.
• Nếu hiện tại ô đang chứa chữ số ~d < 9~, bạn được đổi sang chữ số ~d + 1~.
• Nếu hiện tại ô đang chứa chữ số ~0~, bạn được đổi sang chữ số ~9~.
• Nếu hiện tại ô đang chứa chữ số ~9~, bạn được đổi sang chữ số ~0~.

Hãy tìm cách biến đổi bảng với số lần ít nhất có thể để được một bảng hoàn toàn chia hết cho ~p~.

Input

Dòng đầu tiên chứa ba số nguyên ~m~, ~n~ và ~p~ ~(1 \leq m, n \leq 2000, 1 \leq p \leq 50)~.

Trong ~m~ dòng còn lại, mỗi dòng chứa ~n~ chữ số (từ ~0~ đến ~9~) mô tả bảng số.

Output

Dòng đầu tiên in ra số lần biến đổi bảng nhỏ nhất cần thực hiện để có được một bảng hoàn toàn chia hết cho ~p~.

Trong ~m~ dòng còn lại, mỗi dòng in ra ~n~ chữ số thể hiện bảng số sau khi biến đổi.

Nếu có nhiều cách biến đổi tối ưu, bạn được phép in ra một cách bất kì.

Sắp tát

Bộ test của bài được chia làm các sắp tát như sau:

• Sắp tát ~1~ (~6~ điểm): ~m = 1~
• Sắp tát ~2~ (~12~ điểm): ~m = 2~ và ~p \leq 9~
• Sắp tát ~3~ (~9~ điểm): ~p = 3~
• Sắp tát ~4~ (~12~ điểm): ~p~ là một lũy thừa của ~2~.
• Sắp tát ~5~ (~21~ điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~60~ điểm.

Với mỗi test, bạn được ~50\%~ số điểm nếu tìm ra được số lần biến đổi nhỏ nhất nhưng không tìm ra được bảng số sau khi biến đổi.

Ví dụ

Input 1

4 4 3
2207
1997
0101
2003

Output 1

6
2106 
1996 
0000 
3003

Input 2

3 3 2
846
202
648

Output 2

0
846 
202 
648