Froggie

Time limit2sMemory limit512 MB

Summary

Simulate Froggie hopping across lanes of evenly spaced moving cars on a grid and report whether she exits the top lane safely or gets squished.

Level: Easy3 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

You are recreating the classic 'Frogger' video game. You do not need to worry about sprites, music, or animation, since the game's art team handles those.

Each level has a road with several lanes, and cars travel in both directions. Cars within a lane are evenly spaced and move at the same speed in the same direction. Lane directions alternate, and the top lane moves from left to right.

Froggie starts below the bottom lane and crosses the road from bottom to top. At each time step, Froggie hops one cell up, down, left, or right. The goal is to get Froggie across the road and above the top lane without a car hitting her.

Avoiding Cars

If Froggie enters the path of a moving car, she is squished. Figure D.6 shows one car over two consecutive times. Suppose 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 at speed 3 to the rightmost cell, and Froggie tries to hop into the lane. The lane is four cells wide, so the only safe cell is the leftmost one, where the car had just been. The other three cells would get her squished by the car, ending the simulation.

Figure D.6: A single car across two consecutive time steps, starting at the left and moving right.

Goal

Given a description of the road, the car positions and speeds, and Froggie's starting position and moves, determine the outcome of the simulation. There are two possible outcomes: Froggie safely exits the top lane, or she gets squished.

Before the road, Froggie may move left or right to plan her route. Once she has entered the road, she may only exit through the top. Her path never leaves the left, right, or bottom boundaries of the lanes.

Input

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

Next come $L$ lines, one per lane from top to bottom. Each line has 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 \le O < I \le W$ and $0 \le S \le W$ . All offsets are measured in the direction of the lane's movement.

The final line starts with an integer $P$ ( $0 \le P \le W - 1$ ), then a space, then a string of $M$ characters ( $1 \le M \le L \times W$ ) from the set {U, D, L, R}. $P$ is Froggie's starting position counted from the left, and the string is the sequence of moves (up, down, left, right) she makes.

Output

If Froggie crosses the road and exits from the top lane, print "safe". If she is hit by a car, or she does not end above the road, print "squish".

Examples5

Example 1
Input
```
3 7
0 3 1
1 2 1
2 3 2
2 UUUU
```
Expected output
```
safe
```
Example 2
Input
```
3 6
0 3 1
1 2 1
2 3 2
2 U
```
Expected output
```
squish
```
Example 3
Input
```
3 6
0 3 1
1 2 1
2 3 2
2 UR
```
Expected output
```
squish
```
Example 4
Input
```
3 6
0 3 0
1 2 0
2 3 0
1 UUUU
```
Expected output
```
safe
```
Example 5
Input
```
3 6
0 3 0
1 2 0
2 3 0
1 LRRLUUUU
```
Expected output
```
safe
```