突破包围

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

yzq已经被敌人重重包围了。他必须想办法避开敌人的视线,撤退回实验室,因为现在正值GDUT校赛了,粉多粉多的气球等着他帮忙去派。yzq目前所在的场景可以画成一幅地图,地图由许多小格子组成,共n行m列。其中有些格子是草丛或者障碍物(障碍物不可通过),yzq可以躲在草丛里,不会被敌人发现。这里到处都装着摄像头,敌人可以从电脑上监视整个场景,也就是说yzq一旦离开草丛,马上会被敌人发现,然后就被。。!#$%^&了。但是yzq知道敌人接下来会有k次把监控切换掉(去开心农场偷菜神马的),第i次切换持续的时间是ai秒,yzq每次移动到(上下左右)相邻的格子需要1秒钟。ai秒之后敌人就切换回监控。当然,切换开的这段时间里敌人看不了监控,yzq就可以自由地活动了。yzq想知道他能不能安全地撤退。Can you help him?

Input

 

第一行是一个整数t(t≤50),表示有t组测试数据。

每组测试数据的第一行是两个整数n, m,表示地图共n行m列,2 ≤n,m≤100。

接下来有n行,每行m个字符。字符"*"表示草丛,"y"表示yzq当前所在位置(同时也是一处草丛),"x"表示障碍物(不可经过),字符"."表示空地,"d"表示目的地(yzq移动到这里就算安全撤退)。数据保证草丛的数量不会超过100。

接着的一行是一个整数k(k≤100)和k个整数a1到ak,表示敌人会有k次切换掉监控,第i次切换的时间持续ai(1≤ai≤100000)。

Output

 

输出t行表示t组数据的结果。

对于每组数据,如果yzq可以安全撤退,那么输出”good luck!”,否则输出”poor yzq!”(不用输出引号)

Sample Input

1
5 5
y..x.
.....
.*...
..*..
....d
3 3 2 3

Sample Output

good luck!

Hint

 \"\"

sample的情形如上图所示,yzq开始在1号格子,接下来敌人会有3秒钟时间看不到yzq的行动,yzq可以依次移动到2、3、4号格子,4号格子是草丛,敌人切换回监控的时候看不到躲在4号格子草丛中的yzq。同理,接下来2秒钟和3秒钟yzq可以跑到6号格子,再跑到9号格子安全撤退。yeah。

Source

yzq