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~.