Rắn săn mồi

Putata đang chơi một trò chơi rắn nổi tiếng trên máy tính xách tay của mình, trong đó con rắn di chuyển trên một bàn cờ kích thước $n \times m$. Trên bàn cờ này có thể có một số ô chứa chướng ngại vật. Con rắn có thể được biểu diễn như một dãy các cặp tọa độ xác định vị trí của thân nó: $(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$. Ở đây, $k$ là độ dài của con rắn. Đầu của con rắn là tại $(x_1, y_1)$, đuôi là tại $(x_k, y_k)$, và các phần thân liền kề sẽ nằm trên các ô liền kề nhau theo cạnh.

Trong trò chơi này, con rắn sẽ được điều khiển bằng một chuỗi các lệnh di chuyển. Có 5 loại lệnh mà bạn có thể sử dụng:

L: Di chuyển con rắn một ô sang trái. Đầu của con rắn sẽ di chuyển tới $(x_1, y_1 - 1)$.
R: Di chuyển con rắn một ô sang phải. Đầu của con rắn sẽ di chuyển tới $(x_1, y_1 + 1)$.
U: Di chuyển con rắn một ô lên trên. Đầu của con rắn sẽ di chuyển tới $(x_1 - 1, y_1)$.
D: Di chuyển con rắn một ô xuống dưới. Đầu của con rắn sẽ di chuyển tới $(x_1 + 1, y_1)$.
S: Rút ngắn chiều dài của con rắn đi một đơn vị. Đuôi của con rắn sẽ bị xóa đi, độ dài của con rắn sẽ trở thành $k - 1$. Lưu ý rằng bạn không thể thực hiện lệnh này khi $k = 1$.

Khi đầu của con rắn di chuyển, mỗi phần thân của nó cũng sẽ di chuyển theo. Cụ thể, phần thân thứ $i$ $(2 \leq i \leq k)$ sẽ di chuyển đến vị trí mà phần thân thứ $(i-1)$ ở đó trước khi lệnh được thực hiện. Con rắn không thể di chuyển vào một ô có chướng ngại vật, và không thể di chuyển ra ngoài bàn cờ. Ngoài ra, con rắn không được tự va vào thân của nó, nghĩa là không được có hai phần của thân nằm trên cùng một vị trí.

Trường hợp đặc biệt

Xem xét trường hợp đặc biệt sau: Đầu của con rắn ở vị trí $(x_1, y_1)$, và đuôi ở vị trí $(x_k, y_k)$. Nếu đầu của con rắn đang di chuyển đến $(x'_1, y'_1) = (x_k, y_k)$, thì được phép hoán đổi vị trí đầu và đuôi của con rắn bằng một lệnh duy nhất khi $k = 2$.

Yêu cầu

Bạn sẽ được cung cấp bản đồ của bàn cờ và vị trí của thân con rắn. Gọi $f(i, j)$ là số lệnh tối thiểu để đầu của con rắn có thể đến vị trí $(i, j)$, hoặc $0$ nếu không thể. Nhiệm vụ của bạn là tính giá trị sau:

$
\left( \sum_{i=1}^n \sum_{j=1}^m f(i, j)^2 \right) \mod 2^{32}.
$

Input

Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $k$ $(1 \leq n, m \leq 3000, 1 \leq k \leq \min\{nm, 10^5\})$ - kích thước của bàn cờ và độ dài của con rắn.
Trong $k$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$ $(1 \leq x_i \leq n, 1 \leq y_i \leq m, |x_i - x_{i+1}| + |y_i - y_{i+1}| = 1)$ biểu thị vị trí của phần thân thứ $i$ của con rắn. Đảm bảo rằng tất cả các cặp tọa độ $(x_i, y_i)$ là khác nhau và không có phần thân nào nằm trên ô chứa chướng ngại vật.
Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa một chuỗi có độ dài $m$. Nếu ô $(i, j)$ trống, ký tự thứ $j$ trong dòng thứ $i$ là '.'. Nếu ô $(i, j)$ chứa chướng ngại vật, ký tự đó là '#'.

Output

In ra một số nguyên không âm là đáp án cho bài toán.

Example

Test 1

Input

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

Output

Test 2

Input

Output

Test 3

Input

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

Output

Scoring

Có $25\%$ số test có $n, m, k \leq 5$.
Có $25\%$ số test có $k = 2$.
Có $25\%$ số test có $n, m \leq 300$, $2 < k \leq 5$.
$25\%$ số test còn lại không có ràng buộc gì thêm.

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Scoring

Bình luận