(tabpath.*)

Trên bảng kí tự kích thước \(m \times n\), các hàng được đánh số từ 1 đến \(m\) (từ trên xuống), các cột được đánh số từ 1 đến \(n\) (từ trái sang phải). Ô nằm giao giữa hàng \(i\) và cột \(j\) là ô \((i,j)\). Mỗi ô chứa một kí tự thuộc tập \(\{'A'..'Z','*'\}\). Cụ thể, mỗi ô chứa kí tự chữ cái Latinh in hoa hoặc là kí tự \('*'\).

Xuất phát từ ô \((x,y)\) cần tìm đường đi tới một ô chứa kí tự \('*'\) nào đó trên bảng với chi phí nhỏ nhất theo quy tắc di chuyển như sau:

+ Chỉ được di chuyển sang các ô chung cạnh;

+ Nếu di chuyển sang ô mới chứa kí tự giống với kí tự trong ô hiện tại thì không mất chi phí di chuyển, còn nếu di chuyển sang ô mới chứa kí tự khác với kí tự trong ô hiện tại thì mất chi phí là l.

Yêu cầu: Cho bảng kí tự và \(Q\) ô \(\left( x_{1},y_{1} \right),\ \left( x_{2},y_{2} \right),\ldots,\left( x_{Q},y_{Q} \right)\). Với mỗi ô \(\left( x_{i},y_{i} \right)\), hãy tính chi phí của đường đi từ ô \((x_{i},y_{i})\) đến một ô chứa kí tự \('*'\) nào đó trên bảng có chi phí nhỏ nhất (\(i = 1,2,\ldots,Q)\).

Dữ liệu:

+ Dòng đầu chứa ba số nguyên \(m,\ n,\ Q\);

+ \(m\) dòng tiếp theo, mỗi dòng chứa một xâu độ dài \(n\) mô tả bảng kí tự;

+ \(Q\) dòng tiếp theo, dòng chứa hai số nguyên \(x,\ y\).

Kết quả:

+ Ghi ra \(Q\) dòng, mỗi dòng ghi một số là chi phí của đường đi từ ô \((x,y)\) đến một ô chứa kí tự \('*'\).

Ràng buộc:

• Có 50% số lượng test thỏa mãn điều kiện: \(m,\ n \leq 100;Q \leq 3\);

• Có 25% số lượng test khác thỏa mãn điều kiện: \(m,\ n \leq 1000;Q \leq 3\);

• Có 25% số lượng test còn lại thỏa mãn điều kiện: \(m,\ n \leq 1000;Q \leq m \times n\);

Ví dụ: