Description

One day, Yayun found a treasure map and started to look for the treasure. 

But when she reached the goal marked on the map, there's another treasure map. 

When Yayun was confused, an odd man walked over and told her:

"There are k maps in the world, each (i_th) map points to the next (i+1_th) map. You can find out the treasure locattion if you get the last (k_th) map."

Please help Yayun to find the treasure.

Hint: You must find 1_st, 2_nd, ... k-1_th, k_th maps in order.

Input

The first line contains a integer k, representing the number of maps you must find.

The second line contains two integer n, m representing the height and width of the map.

The next n lines, each line contains m integers. 

• -1: you cannot pass here.
• 0: there is a road here and you can pass.
• 2021: the starting point. You can also pass here agin.
• other integer x: the x_th map. You can also pass here.

For all testcases:

(2/6): no -1 on the map, k = 1, 1 <= n, m <= 200

(1/6): k = 1, 1 <= n, m <= 200

(1/6): no -1 on the map, 1 <= k <= 100, 1 <= n, m <= 200

(1/6): 1 <= k <= 100, 1 <= n, m <= 200

(1/6): 1 <= k <= 100, 1 <= n, m <= 200

Output

The minimum steps to find the k_th map.

If you cannot find the k_th map, output -1.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss