Minh đang chơi một trò chơi mê cung, trong trò chơi cậu phải điều khiển nhân vật của mình thoát khỏi một mê cung hai chiều gồm $N \times N$ ô.

Vị trí xuất phát của Minh ở góc trên bên trái, cậu cần đến được ô ở góc dưới bên phải để thoát khỏi mê cung.

Mỗi bước, cậu có thể di chuyển sang ô kề trên, dưới, trái, phải (với điều kiện ô đích có thể đi qua được).

Trong mê cung có những ô Minh có thể đi qua, ta ký hiệu là .;

Có những ô là tường, Minh không thể đi qua, ta ký hiệu là #.

Ngoài ra, có những ô có cạm bẫy, ta ký hiệu là X. Trừ khi Minh đang ở trạng thái bất tử, nếu không thì không thể đi qua.

Có những ô có vật phẩm bất tử, ta ký hiệu là %.

Khi Minh đến ô đó lần đầu tiên, cậu tự động nhận được trạng thái bất tử, trạng thái bất tử kéo dài $K$ bước.

Sau đó nếu đến ô này lần nữa thì sẽ không nhận được trạng thái bất tử nữa.

Khi ở trạng thái bất tử, có thể đi qua ô có cạm bẫy, nhưng không tháo gỡ / phá hủy cạm bẫy, tức là cạm bẫy vẫn ngăn nhân vật không có trạng thái bất tử đi qua.

Cho mê cung, hãy tính số bước ít nhất để Minh thoát khỏi mê cung.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$. $(1 \le N \le 1000, 1 \le K \le 10)$.

$N$ dòng tiếp theo chứa một ma trận $N\times N$.

Ma trận đảm bảo góc trên bên trái và góc dưới bên phải là ..

Dữ liệu ra

Một số nguyên biểu thị đáp án. Nếu Minh không thể rời khỏi mê cung, in ra $-1$.

Ví dụ 1

Input

5 3
...XX
##%#.
...#.
.###.
.....

Output

10

Ví dụ 2

Input

5 1
...XX
##%#.
...#.
.###.
.....

Output

12

Ghi chú

Nguồn: Lanqiao Cup 2018, vòng chung kết quốc gia lần thứ 9