题目描述

原野是一个矩形，P 表示平地，L 表示湖泊。鸟人要从左上角到右下角，只能停在平地。每次可以上下左右步行一格，用时1；也可以沿这四个方向之一直线飞行若干格，落在平地，飞行不论多远都用时1。所有飞行距离之和不能超过 $D$。求最短时间。

输入格式

第一行三个整数 $m,n,D$，分别为行数、列数和飞行总距离上限。接下来 $m$ 行，每行 $n$ 个字符。

输出格式

输出最短时间。无法到达（包括起点或终点为湖泊）则输出 impossible。

样例

1 3 2
PLP

1

数据范围

$1\le m,n\le100$，$0\le D\le100$。