Giấc mơ của Bessie

Cho mê cung $N\times M$ ô, mỗi ô có một màu:

• Đỏ (0): Không thể đi qua.
• Hồng (1): Đi qua bình thường.
• Cam (2): Đi qua và được "mùi cam".
• Xanh (3): Chỉ đi qua được nếu đang có mùi cam.
• Tím (4): Trượt tiếp theo hướng đang đi cho đến khi gặp ô không tím hoặc chướng ngại vật. Mất mùi cam khi trượt trên ô tím.

Bắt đầu từ ô $(1,1)$ (góc trên trái), tìm số bước ít nhất để đến ô $(N,M)$ (góc dưới phải). Mỗi bước di chuyển sang ô kề (trên, dưới, trái, phải). Nếu không thể đến được, in $-1$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $M$.
• $N$ dòng tiếp theo: mỗi dòng $M$ số nguyên ($0$-$4$) — màu các ô.

Dữ liệu ra

Một số nguyên duy nhất — số bước ít nhất, hoặc $-1$.

Ràng buộc

• $1\le N,M\le 1000$
• Ô $(1,1)$ và $(N,M)$ luôn là hồng (1).

Ví dụ