Một xe tự hành đi giao hàng sẽ di chuyển trong một kho hàng hình chữ nhật gồm R hàng và C cột. Mỗi ô trong kho có thể là:

• Ô trống là ô xe tự hành có thể di chuyển qua.
• Ô chứa vật cản là ô xe tự hành không thể đi qua.
• Ô bắt đầu là vị trí ban đầu của xe tự hành.
• Ô đích giao hàng là vị trí mà xe tự hành cần đến.

Xe tự hành có thể di chuyển theo bốn hướng (lên, xuống, trái, phải). Tuy nhiên, do giới hạn năng lượng của bánh xe, trong mỗi lần di chuyển, xe tự hành chỉ có thể đi tối đa K ô liên tiếp theo cùng một hướng và không thể vượt qua vật cản.

Yêu cầu:

Hãy xác định số lần di chuyển ít nhất để xe tự hành có thể đi từ vị trí bắt đầu đến được vị trí giao hàng. Nếu không thể đến được in ra -1.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím)

• Dòng đầu: 3 số nguyên \(R, C, K (R x C \leq 10^6; K \leq 10^6)\)

• Tiếp theo là R dòng, mỗi dòng có C ký tự mô tả bản đồ:

  • S: vị trí xe tự hành bắt đầu
  • D: vị trí xe tự hành giao hàng
  • #: tương ứng là ô chứa vật cản
  • .: tương ứng là ô trống

Kết quả:

In ra số lần di chuyển ít nhất để xe tự hành đến vị trí giao hàng hoặc in ra -1 nếu không thể.

Ví dụ:

Input 1:

 4 5 2
S..#.
.#...
..#.D
.....

Output 1:

4

Input 2:

 2 5 10
S#...
...#D

Output 2:

5

Input 3:

 4 5 2
S.#..
###..
..#D.
.....

Output 3:

-1

Giới hạn:

• Được 40% số điểm ứng với các test thỏa mãn: \(R x C \leq 200, K \leq 10 \)
• Được 60% số điểm ứng với các test thỏa mãn: \(R x C \leq 10^6; K \leq 10^6\)