Hàng rào

Time limit: 1.0s , Memory limit: 256M , Points: 100 (partial)

Khu vườn Harden có kích thước $n \times n$ ~n \times n~ ô vuông, các hàng được đánh số từ $1$ ~1~ đến $n$ ~n~ từ trên xuống dưới và các cột được đánh số từ $1$ ~1~ đến $n$ ~n~ từ trái sang phải. Tại mỗi ô vuông có thể là đất trống $($ ~(~ký hiệu . $)$ ~)~ hoặc tảng đá $($ ~(~ký hiệu # $)$ ~)~ hoặc được trồng một bông hoa có giá trị từ $1$ ~1~ đến $9$ ~9~ $($ ~(~ký hiệu bởi ký tự chữ số $)$ ~)~.

Bob muốn xây dựng một hàng rào hình vuông với độ dài cạnh bằng $k$ ~k~, hàng rào phải nằm trong khu vườn. Bob muốn trên cạnh của hàng rào không được có bất ký tảng đá hay bông hoa nào, nhưng tảng đá và bông hoa vẫn có thể nằm ở bên trong hàng rào. Giá trị của một hàng rào bằng tổng giá trị các bông hoa nằm bên trong hàng rào đó.

Bạn hãy giúp Bob xác định giá trị lớn nhất của hàng rào mà Bob có thể xây, trả lời với $m$ ~m~ câu hỏi.

Input

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $m$ ~m~ là kích thước khu vườn và số lượng câu hỏi $(5 \le n \le 1000$ ~(5 \le n \le 1000~ $;$ ~;~ $1 \le m \le 200)$ ~1 \le m \le 200)~.
$n$ ~n~ dòng tiếp theo, mỗi dòng chứa $n$ ~n~ ký tự mô tả khu vườn, các ký tự có thể là . $($ ~(~đất trống $)$ ~)~ hoặc # $($ ~(~tảng đá $)$ ~)~ hoặc ký tự chữ số từ 0 đến 9 $($ ~(~giá trị bông hoa $)$ ~)~.
$m$ ~m~ dòng tiếp theo, mỗi dòng chứa một số nguyên $k$ ~k~ là kích thước của hàng rào $(3 \le k \le n)$ ~(3 \le k \le n)~.