Sau khi ăn quá nhiều trái cây trong bếp của Farmer John, cô bò Bessie bắt đầu có những giấc mơ rất kỳ lạ! Trong giấc mơ gần đây nhất, cô bị mắc kẹt trong một mê cung có dạng lưới \(N\times M\) ô (\(1\le N,M\le1\,000\)). Cô bắt đầu ở ô trên cùng bên trái và muốn đến ô dưới cùng bên phải. Khi đứng trên một ô, cô có thể di chuyển sang các ô kề theo bất kỳ hướng nào trong bốn hướng chính.

Nhưng khoan đã! Mỗi ô có một màu, và mỗi màu có một tính chất khác nhau! Bessie chỉ nghĩ đến thôi cũng thấy đau đầu:

• Nếu một ô có màu đỏ, ô đó không thể đi qua.
• Nếu một ô có màu hồng, cô có thể đi trên đó như bình thường.
• Nếu một ô có màu cam, cô có thể đi trên đó như bình thường, nhưng ô này sẽ khiến Bessie mang mùi cam.
• Nếu một ô có màu xanh lam, ô đó có cá piranha và chúng chỉ cho Bessie đi qua nếu cô mang mùi cam.
• Nếu một ô có màu tím, Bessie sẽ trượt sang ô tiếp theo theo hướng đang đi (trừ khi cô không thể đi qua ô đó). Nếu ô tiếp theo cũng có màu tím, Bessie sẽ tiếp tục trượt cho đến khi đáp xuống một ô không màu tím hoặc đụng phải một ô không thể đi qua. Trượt qua một ô được tính là một bước di chuyển. Các ô màu tím cũng sẽ loại bỏ mùi của Bessie.

(Nếu bạn thấy các ô màu tím khó hiểu, ví dụ sẽ minh họa cách chúng hoạt động.)

Hãy giúp Bessie đi từ ô trên cùng bên trái đến ô dưới cùng bên phải với ít bước di chuyển nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), biểu thị số hàng và số cột của mê cung.

\(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên biểu thị mê cung:

• Số nguyên 0 là một ô màu đỏ.
• Số nguyên 1 là một ô màu hồng.
• Số nguyên 2 là một ô màu cam.
• Số nguyên 3 là một ô màu xanh lam.
• Số nguyên 4 là một ô màu tím.

Các số nguyên ở ô trên cùng bên trái và ô dưới cùng bên phải luôn là 1.

Dữ liệu ra

In một số nguyên duy nhất biểu thị số bước di chuyển ít nhất Bessie cần để vượt qua mê cung, hoặc -1 nếu không thể làm được.

Ví dụ

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

10

Nguồn

USACO 2015 December Contest, Gold - Bessie's Dream: https://usaco.org/index.php?page=viewproblem2&cpid=575

Tác giả: Nathan Pinsker, inspired by the game "Undertale".