Get Out 'Da Way!

Time Limit: 1 Second    Memory Limit: 32768 KB

Introduction

Boudreaux and Thibodaux have just seen the Matrix, and are arguing whether or not it would actually be possible to dodge bullets if you moved fast enough. Boudreaux is used to hunting nutria with buckshot, and maintains that most bullet spreads should make it impossible to dodge all the bullets. Thibodaux is still doing kung-fu in his head, and is sure that if you could move fast enough it would be possible to dodge the bullets. Boudreaux is getting fed up, and is about ready to prove his point with some empirical testing. Your job is to come up with a way to prove or disprove this hypothesis for different scenarios using computer simulations, which are much safer than the methods that Boudreaux has in mind.

Input

Input to this problem will consist of a (non-empty) series of up to 20 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 5 components:

Start line - A single line, "START N", where N is a positive integer in the range 1 <= N <= 10 which indicates the number of bullets fired at the target.

Target Velocity - A single line representing the velocity of the target.

Bullet Velocity List - A non-empty set of up to 10 lines. Each line will contain the velocity of a single bullet.

Target - A nonempty series of up to 30 lines. Each line will consist of up to 30 characters (not counting the end-of-line). Each non-whitespace character represents a piece of the target that can be hit by a bullet. The target will not contain numbers, asterisks, or commas, but any other characters may be used. The target grid is assumed rectangular for the purposes of determining its center, and its dimensions are that of the longest row/column (this will not exceed 30 blocks in either direction). Each block of the target grid is 10cm X 10cm.

End line - A single line, "END"

Output

Find out if the target got out 'da way. A hit occurs when any bullet passes through a grid square with mass in it. For the sake of simplicity, the target can be assumed to be two dimensional, and the bullets volumeless. Also, Boudreaux and Thibideaux don't even know what precision means, they just make sure to calculate to at least four decimal places. (In other words, don't worry about precision edge detection. Just keep the math simple and use very precise numbers to minimize error. You'll find hits in the correct places.)

For each data set, there will be exactly one output set, and there will be exactly one blank line separating output sets.

An output set will take one of two forms:

If no bullets hit mass-containing parts of the target, your output will be, "Got Out Da Way!"

Otherwise (if at least one hit occurred), your output will be the Target, with all hit blocks replaced with asterisks ('*').

Sample Input

START 3
-10,-2,1
300,14.5,-20
350,-80,0
400,28.75,26
     @@@@      n
     #^^#     oU
      ##     o
  ooooooooooo
  o oooooo
  o  oooo
 o   DDDD
oo   DDDD
     D  D
     D  D
    TT  TT
    TT  TT
  
END
START 2
-10,-2,1
300,14.5,-20
350,-80,0
     @@@@      n
     #^^#     oU
      ##     o
  ooooooooooo
  o oooooo
  o  oooo
 o   DDDD
oo   DDDD
     D  D
     D  D
    TT  TT
    TT  TT

END

Sample Output

     @@@@      *
     #^^#     oU
      ##     o
  ooooooooooo
  o oooooo
  o  oooo
 o   DDDD
oo   DDDD
     D  D
     D  D
    TT  TT
    TT  TT


Got Out Da Way!

Submit

Source: South Central USA 2001