题目描述

 勇敢的SwordHoly 完成了任务之后，正在迅速的向自己的基地撤退。但由于后面有着一大群追兵，所以SwordHolys 尽快地返回基地，否则就会被敌人逮住。
	终于，SwordHoly来到了最后一站：千岛湖，穿过这里就可以回到基地了。然而敌人依然紧追不舍。不过，千岛湖的地理条件对SwordHoly十分有利，众多的湖泊随处分布。敌人需要绕道而行。但SwordHoly有变成鹰的特殊能力，使得他能轻轻松松地飞越湖面。当然，为了保证安全起见，SwordHoly还是决定找一条能最快回到基地的路。
假设千岛湖是一个m*n的矩阵，它有两种地形，P表示小岛，L表示湖泊。SwordHoly只能停留在小岛上。他目前的位置在左上角（1，1）处。而目的地为右下角的(m,n)。SwordHoly可以向前后左右4个方向移动或者飞行，每移动1格需要1单位时间。而飞行的时间主要花费在变形上，飞行本身时间消耗很短，所以无论一次飞行多远的距离，都只需要1单位时间。飞行的途中不能变向，并且以此飞行最终必须要降落在平地上。当然，由于受到能量的限制，SwordHoly不能无限制的飞行，他总共最多可以飞行的距离为D。在知道了以后了以上的信息后，请你帮助SwordHoly计算一下，他最快到达基地所需要的时间。

输入要求

第一行是3个正整数，m(1<=m<=100),n(1<=n<=100),D(1<=D<=100).表示千岛湖是m*n的矩阵，SwordHoly最多只能飞行距离为D。
接下来的m行每行有n个字符，相互之间没有空格。P表示当前位置是平地，L则表好似湖泊。假定(1,1)和(m,n)一定是平地。

输出要求

一个正整数，表示SwordHoly能到达基地的最短时间。如果无法到达则输出impossible

输入样例

4 4 2
PLLP
PPLP
PPPP
PLLP

输出样例

5

提示

来源