Problem D
Froggie

Photo from Wikipedia

You are recreating the classic ‘Frogger’ video game. You do not need to worry about sprites, music, or animation (that is left to the game’s art team).

Each level consists of a road with multiple lanes, with cars traveling in both directions. Cars within each lane are evenly-spaced and move at the same speed and in the same direction. Lane directions alternate, with the top lane moving left to right.

‘Froggie’ starts below the bottom lane and she travels across the road from the bottom to the top. At each time step, Froggie hops one space in one of four directions: up, down, left, or right. The goal of the game is to get Froggie across the road and above the top lane without her getting hit by a car.

Example

Consider the first sample input, where Froggie hops upward four times. The road has three lanes and a width of $7$. Froggie starts below the road in the third cell. Cars in the top and bottom lanes are spaced at an interval of $3$, and the middle lane has an interval of $2$. The cars in the top two lanes move at a speed of $1$, while those in the bottom lane move at a speed of $2$. See Figure 1.

At time $1$ Froggie hops upward and the cars move. The cars in the top and middle lanes each move one space, and the cars in the bottom lane each move two spaces. See Figure 2. After this first hop, Froggie is still safe. She now sits where a car was, and has avoided the path of the car as it travels. Notice that cars exit the simulated area as they travel off the grid, and also new cars also enter (at times that preserve each lane’s interval).

At time $2$, Froggie hops upward again as the cars continue to move. After hopping into the middle lane, Froggie could move left with this lane’s traffic (traffic in this lane moves left at a speed of $1$). See Figure 3.

At time $3$, Froggie hops upward a third time, reaching the top lane. See Figure 4. Finally, at time $4$, with a final upward hop, Froggie exits the road to safety. See Figure 5.

Avoiding Cars

If Froggie enters the path of a moving car, or jumps into a stationary car, she is squished. Consider Figure 6, which is a bit different than earlier figures in that it shows one car over two successive times. Let’s say that at time $t$ the car is in the leftmost cell and Froggie is not in this lane. At time $t+1$, the car moves with a speed of $3$ to the rightmost cell, and Froggie attempts to hop into the lane shown. Since the width of the lane is four, the only safe place to hop is the leftmost cell (where the car had just been). The other three cells would cause her to be squished by the car shown, ending the simulation.

Goal

Given a description of the road, car positions and speeds, and Froggie’s starting positions and moves, determine her outcome after the simulation. There are two possible outcomes: safely exiting the top lane or getting squished.

In order to better plan her travel, Froggie may move left or right before entering the road. Once Froggie has entered the road she may only exit through the top of the road. That is, Froggie’s path never exits the left, right, or bottom lane boundaries.

Input

Each input describes one simulation. The first line of input contains two integers separated by a space: $L$ and $W$. The number of lanes is given by $L$ ($1 \leq L \leq 10$), while $W$ ($3 \leq W \leq 20$) defines the width (in number of cells) of the grid.

This is followed by $L$ lines each describing the car configuration for a lane (from top to bottom). Each line contains three integers: $O$, the starting offset of the first car; $I$, the interval between cars; and $S$, the speed of the cars. The bounds are $0 \leq O < I \leq W$ and $0 \leq S \leq W$. All offsets should be computed based on the direction of lane movement. That is, in lanes that move right, offset $0$ is the leftmost cell and offset $W-1$ is the rightmost cell in that lane, while in lanes that move left, offset $0$ is the rightmost cell and offset $W-1$ is the leftmost cell in that lane.

The final line of input starts with a single integer, $P$ ($0 \leq P \leq W - 1$) followed by a space and then a string of $M$ characters ($1 \leq M \leq L \cdot W$) from the set $\{ \textrm{U}, \textrm{D}, \textrm{L}, \textrm{R} \} $. $P$ defines the starting position of Froggie, starting from the left. The string of characters defines the sequence of moves (up, down, left, right) that Froggie makes during the simulation.

Output

If Froggie successfully crosses the road (exiting the road from the top lane), output “safe”. If Froggie is hit by a car, or does not end above the road, output “squish”.

3 7
0 3 1
1 2 1
2 3 2
2 UUUU

safe

3 6
0 3 1
1 2 1
2 3 2
2 U

squish

3 6
0 3 1
1 2 1
2 3 2
2 UR

squish

3 6
0 3 0
1 2 0
2 3 0
1 UUUU

safe

3 6
0 3 0
1 2 0
2 3 0
1 LRRLUUUU

safe