Time Limit: 5000 MS Memory Limit: 65536 K
Recently, yjx, zjm1992 and mario is crazying on a game called FieldRunners.
Here, we simplify the game. We give a field of N * N grids. There are 3 kinds of weapons in the field : Gun, Missile and Flamethrower. Each kind of weapon has a ATK : Gun(1 HP), Missile(3 HP), Flamethrower(5 HP). In the meantime, each weapon has its own attack range in 4 directions of up, down, left and right: Gun(1 grid), Missle(2 grids), Flamethrower(3 grids).
When Mario steps into a grid which is in the attack range of a weapon, he will lose the corresponding HP. If Mario's HP is 0, he will die. There are many weapons in the field, Mario could only step into the girds which doesn't has weapon on it. Now, Mario is at top-left corner (1, 1), and a nice girl is at the bottom-right corner (n, n). He only has M HP, could he meet the girl alive ?
There will be some cases. Each case contains N+1 lines. First line contains 2 integers N(N<100) and M(M<10000). Next N lines represent the N rows from top to bottom, with each line having precisely N characters, from left-to-right, describing the field.
We describe the field using following symbols:
'.' -> a space Mario can step into
'G' -> here is a Gun
'M' -> here is a Missile
'F' -> here is a Flamethrower
For each case, output one line. If Mario can reach(n, n), output "Girl~", else output "Die..".