Một công ty sử dụng rô bốt để xếp hàng hóa vào kho. Một con rô bốt phải xếp một kiện hàng từ vị trí bốc hàng và đặt kiện hàng vào một vị trí dỡ hàng nhất định. Mỗi vị trí bốc hàng chứa duy nhất một kiện hàng, và mỗi vị trí dỡ hàng cũng chỉ chứa được duy nhất một kiện hàng. Rô bốt có thể mang tận \(n\) kiện hàng một lúc.
Bản đồ nhà kho được biểu diễn dưới dạng ma trận số nguyên hai chiều:

• Các số \(0\) biểu thị các bức tường mà rô bốt không thể đi qua
• Các số \(1\) biểu thị các vị trí trống mà rô bốt có thể đi qua dễ dàng
• Số \(2\) biểu thị vị trí nơi mà rô bốt đang đứng
• Các số \(3\) biểu thị những vị trí bốc hàng (nơi rô bốt có thể đi qua)
• Các số \(4\) biểu thị những vị trí dỡ hàng (nơi rô bốt có thể đi qua dù vị trí đó đã chứa một kiện hàng)

Tính và trả về con đường ngắn nhất của rô bốt, chắc chắn rằng rô bốt có thể lấy hết các kiện hàng và đặt chúng vào nhà kho. Nếu không tồn tại phương án nào, trả về \(-1\).

Input

• Dòng đầu tiên chứa ba số nguyên \(R, C, n\) tương ứng là số hàng, số cột của bản đồ và số kiện hàng tối đa rô bốt có thể mang cùng lúc.
• \(R\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự có độ dài \(C\) chỉ bao gồm các số \(0, 1, 2, 3, 4\) biểu thị bản đồ nhà kho.
• Chỉ có một vị trí bắt đầu của rô bốt trên bản đồ (ký tự \(2\)).

Output

• In ra số nguyên biểu thị số bước di chuyển nhỏ nhất mà rô bốt nên đi. Nếu không có phương án nào, trả về \(-1\).

Example

6 5 1 
11011
20011
10411
10313
11114
11111

11

3 4 1 
2103
1101
1104

-1

Constraints

• \(1 \le R,C \le 40.\)
• \(1 \le n \le 5.\)
• Số điểm bốc và dỡ hàng không quá \(20\).

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(R, C \le 10\), tổng số điểm bốc và dỡ hàng \(P = 2\), \(n = 1\).
• Subtask \(2\) (\(25\%\) điểm): \(R, C \le 20\), tổng số điểm bốc và dỡ hàng \(P \le 6\), \(n = 1\).
• Subtask \(3\) (\(25\%\) điểm): \(R, C \le 40\), tổng số điểm bốc và dỡ hàng \(P \le 20\), \(n = 1\).
• Subtask \(4\) (\(30\%\) điểm): Không có ràng buộc gì thêm.