题目描述

在一片广阔的土地上有一个鸟人,他需要从这里穿过原野回到基地。这片原野上有平地(\(P\))。有湖泊(\(L\))。因为鸟人可以飞，所以有的时候，他可以飞越湖泊。现在，鸟人需要用最快的时间回到基地。
假设原野是一个 \(m×n\) 的矩阵，有两种地形，用 \(P\) 和 \(L\) 表示。鸟人只能停留在平地上。他目前处在 \((1,1)\) 这个位置，而目的地是 \((m,n)\)。他可以向上、下、左、右四个方向移动,或者飞行每移动一格需要 \(1\) 个单位时间。而飞行无论飞多远,都只需要 \(1\) 个单位时间，飞行的途中不可以改变方向。也就是说，飞行也只能是上、下、左、右四个方向，并且一次飞行最终必须降落在平地上。当然，受到能量的限制,鸟人不能无限制地飞行,他总共最多可以飞行的距离为 \(D\)。

格式

输入格式

第 \(1\) 行是 \(3\) 个整数 \(m、n\) 和 \(D,3\) 个数都不超过 \(100\)。下面是一个 \(m×n\) 的字符矩阵,表示原野。

输出格式

输出一行一个整数表示最短时间。如果无法到达,输出"\(\texttt{impossible}\)"

样例1

样例输入1

4 4 2
PLLP
PPLP
PPPP
PLLP

样例输出1

5