题目描述

“小燕子，穿花衣，年年春天来这里~~~” ，多么熟悉的童谣！燕子在春天会回到北方。假设现在有一只燕子，它需要穿过旷野回到鸟巢。旷野上有平地（$P$）和湖泊（$L$）。

燕子可以飞，所以有的时候它可以飞越湖泊。现在，燕子需要用最快的时间回到鸟巢。假设旷野是一个 $m×n$ 的矩阵，有两种地形，用 $P$ 和 $L$ 表示。燕子只能停留在平地上。它目前处在（1，1）这个位置，而鸟巢的位置是（$m，n$）。它可以向上、下、左、右四个方向移动，或者飞行。每移动一格需要 $1$ 个单位时间。而飞行无论飞多远，都只需要 $1$ 个单位时间。飞行的途中不可以改变方向。也就是说，飞行也只能是上、下、左、右四个方向，并且一次飞行最终必须降落在平地上。当然，受到身体所需能量的限制，燕子不能永远地飞行，它总共最多可以飞行的距离为 $D$。

输入格式

第 1 行是 $3$ 个整数 $m$、$n$ 和 $D$，3 个数都不超过 100。下面是一个 $m×n$ 的字符矩阵，表示旷野。

输出格式

一个整数表示最短时间。如果无法到达，输出 “impossible” 。

样例

4 4 2
PLLP
PPLP
PPPP
PLLP

5