Hệ thống lưới điện được mô hình hóa bao gồm ~n~ nút quan trọng được đánh số từ 1 đến ~n~, đại diện cho các nhà máy điện, trạm biến áp, trung tâm điều độ, và các điểm phụ tải trọng yếu. Thời gian ước tính để thiết lập, kiểm tra và ổn định kết nối giữa nút ~i~ và nút ~j~ là ~d_{ij}~.

Trong số ~n~ nút này, có ~m~ nút ~f_1, f_2, \dots, f_m~ được xác định là các nút cốt lõi của hệ thống. Kỹ sư Minh được giao nhiệm vụ lập kế hoạch cho ~q~ quy trình khôi phục điện khẩn cấp. Mỗi quy trình thứ ~k~ có mục tiêu là tái cấp điện hoặc đảm bảo vận hành ổn định cho một nút đích ~v_k~, bắt đầu từ một nút xuất phát ~u_k~.

Để đảm bảo tính ổn định và an toàn cho toàn hệ thống, một yêu cầu bắt buộc đối với mỗi quy trình khôi phục là: phải đảm bảo tất cả ~m~ nút cốt lõi đã được kích hoạt, kiểm tra và đưa vào trạng thái vận hành ổn định trước khi hoàn tất việc kết nối và cấp điện/ổn định cho nút đích cuối cùng ~v_k~. Thứ tự kích hoạt/kiểm tra các nút cốt lõi này là tùy chọn, nhưng tất cả đều phải được hoàn thành. Các đội kỹ thuật có thể cần di chuyển qua lại giữa các nút nhiều lần trong quá trình thực hiện.

Yêu cầu: Hãy lập kế hoạch cho mỗi quy trình sao cho tổng thời gian cần thiết (bao gồm thời gian di chuyển, kiểm tra, kích hoạt kết nối) là nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên ~n, m, q~ (~1 \le n \le 1500, 1 \le m \le 17, 1 \le q \le 190000~);
• Dòng thứ hai chứa ~m~ số nguyên phân biệt thể hiện chỉ số của ~m~ nút cốt lõi;
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên ~d_{i1}, d_{i2}, \dots, d_{in}~ (~1 \le d_{ij} \le 1000~; ~i \ne j~), trong đó ~d_{ij}~ là thời gian ước tính để thiết lập/ổn định kết nối từ nút ~i~ đến nút ~j~. Dữ liệu vào đảm bảo ~d_{ii} = 0~;
• Trong ~q~ dòng cuối cùng, dòng thứ ~k~ chứa hai số nguyên ~u_k, v_k~ (~1 \le u_k, v_k \le n~) lần lượt là nút xuất phát và nút đích của quy trình khôi phục thứ ~k~.

Output

• Ghi ra ~q~ số nguyên trên một dòng (các số cách nhau một dấu cách), số nguyên thứ ~k~ là tổng thời gian nhỏ nhất để hoàn thành quy trình khôi phục thứ ~k~.