Bob被困在地球的一片树林内，树林里有各种各样的怪物，你必须帮助Bob尽快逃离森林。 现在，我们将这个问题简化并说明一下： 　　（１）森林是一个N行M列的图。森林的最外一圈以及森林里的某些地方有障碍，Bob 不可能穿过障碍以及后文所提到的食人花； （２）Bob初始时位于地图的第X1行第Y1列，他每次可以往上下左右中的任一方向 移动一格，他的目标是到达出口（地图的第X2行Y2列）顺利逃生； （３）森林中有一种可怕的食人花，它们的嘴始终朝着一个方向，并会吃掉经过它们的 嘴朝向的第一个格子中的的一切东西——我们称这个格子被食人花控制——因此，Bob可以从食人花不能控制的前面或两侧或后面通过； （４）尽管Bob可以绕过食人花前进，但很多情况下，Bob还是不得不经过食人花的面前。万幸的是，Bob随身带了K个苹果，他可以把苹果丢在与自己相邻的四个方格中的任一个中；如果苹果丢在了食人花的面前，食人花就会到当仁不让地一口吞下，因为吃了苹果，食人花就不会吃掉Bob,此时Bob就可以快速通过食人花控制的方格。 （５）另外，我们规定，食人花并不相互攻击，如果有一个方格被两朵食人花控制，“团结友爱”的食人花会各吃掉半个苹果，因此Bob只须扔一个苹果即可通过——前提是此时Bob手中必须有苹果。 （６）Bob的起点和终点一定在空地上，且坐标一定不同。 现在，给你Bob的初始坐标（行、列），出口坐标，Bob携带的苹果个数以及地图，因为Bob比较贪吃，所以他希望扔掉的苹果越少越好，现在请你告诉Bob至少需要多少苹果才能顺利逃生，如果Bob无法逃出森林，则输出一行“Bob lost his life in the forest.”。

第1行为两个整数N、M，中间用一个空格隔开，代表森林的行列数；（3<=N，M<=40） 第2行有用空格隔开的四个整数X1，Y1，X2，Y2，分别代表起点和终点的坐标；（起点与终点是不同的两个点） 第3行有一个整数K，代表Bob随身携带的苹果个数。(0<=K<=100) 从第4行至第N+3行描绘了森林地图，其中“0”代表障碍，“^”、“<”、“V”、“>”分别代表口朝着上、左、下、右的食人花，“ ”代表空地。

如果Bob无法逃出森林，则输出一行“Bob lost his life in the forest.”；否则，输出至少需要的苹果数。

5 9
2 2 4 7
3
000000000
0  <    0
0  < 0^ 0
0>   0  0
000000000

3

【样例说明】
Bob在（2，2）位置，——>（3，2），往（3，3）丢一个苹果，——>（3，3）,往（4，3）丢 一个苹果，——>（4，3）——>（4，4）——>（4，5）——>（3，5）——>（2，5）——>（2，6）, 往（2，7）丢 一个苹果，——>（2，7）——>（2，8）——>（3，8）——>（4，8）——>（4，7）,一共丢了3个苹果。