Siru's Department Store Tour

Siru went to a department store with her parents. Her parents have a lot of shopping to do and need to visit many places. Walking around with them is too tiring for Siru, so she wants to sit down on a chair and rest.

The department store is a grid with $N$ rows and $M$ columns. Each move to an adjacent cell up, down, left, or right costs 1 stamina. Siru starts at her current position and wants to walk to one of the chairs scattered around the store and sit down. Siru cannot leave the department store, because her parents would scold her.

The store has pillars that hold up the building and mannequins that display clothes. Siru cannot move into a cell with a pillar. She is afraid of mannequins, so she also avoids every cell whose distance to a mannequin is $K$ or less. The distance between cells $(r_x, c_x)$ and $(r_y, c_y)$ is $\vert r_x-r_y \vert + \vert c_x-c_y \vert$. However, Siru sets out with her parents, so she can leave even if her starting cell is within distance $K$ of a mannequin.

Her legs hurt, so she wants to reach a chair while spending as little stamina as possible. Find the minimum stamina Siru spends.

The first line contains the number of rows $N$, the number of columns $M$, and the distance $K$ that must be kept from mannequins, separated by spaces. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$)

The next $N$ lines each contain $M$ numbers, describing the store from top to bottom. An empty cell is 0, a pillar is 1, a chair is 2, a mannequin is 3, and Siru's starting position is 4. The starting position appears exactly once, and it holds no pillar, chair, or mannequin.

If Siru can reach a chair, print the minimum stamina she spends. If she cannot reach any chair, print -1.

Python users are recommended to submit with PyPy.