题目背景

森林大火正在威胁你的栖息地。作为一只袋鼠，你需要尽快通知同伴们撤离，然后前往安全区域。

你一开始静止不动。接下来，你会通过一系列跳跃依次到达其他袋鼠所在的位置，最后跳到安全区域并停下来。

题目描述

给定一个 $r \times c$ 的网格。每个格子可能是空地，也可能是灌木丛。袋鼠只能落在网格内的非灌木格子上。

一次跳跃由两个整数位移组成：

• 向北移动的距离；
• 向东移动的距离。

位移可以为负数，因此也可以向南或向西移动。若第 $i$ 次跳跃的位移为

$$(v_{x,i}, v_{y,i}),$$

则下一次跳跃的位移必须满足

$$|v_{x,i+1}-v_{x,i}|\le 1,$$ $$|v_{y,i+1}-v_{y,i}|\le 1.$$

你初始静止，因此可认为第 $0$ 次跳跃的位移为 $(0,0)$。

网格中：

• . 表示空地；
• # 表示灌木丛，不能落在上面；
• 0 表示你的起点；
• 1 到 k 表示需要按顺序通知的其他袋鼠；
• 字符 k+1 表示安全区域。

你必须按 1,2,\ldots,k 的顺序通知所有袋鼠，然后到达安全区域。最后必须完全停下，因此最后一次跳跃的起点和终点都必须是安全区域，也就是最后一次跳跃位移为 $(0,0)$。

请计算完成这一过程所需的最少跳跃次数。如果无法完成，输出 impossible。

输入格式

第一行包含三个整数 $r,c,k$，分别表示网格行数、列数和需要通知的其他袋鼠数量。

接下来 $r$ 行，每行包含 $c$ 个字符，描述网格。

输出格式

如果可以到达安全区域并停下，输出一个整数，表示最少跳跃次数。

否则输出：

impossible

样例 1

输入

5 5 1
0..2.
.###.
.....
.....
.#.#1

输出

9

样例 2

输入

2 2 2
03
12

输出

4

样例 3

输入

1 5 1
.0#21

输出

8

样例 4

输入

3 4 1
#0##
#.#2
1###

输出

impossible

数据范围

对于所有测试数据：

$$1 \le r,c \le 50,$$ $$1 \le k \le 5.$$