You feel your energy start to dip, and decide to hit the arcade at the casino's entrance. Here, you find a gnarly-looking Snake game.

In Snake, you control a snake (who would've guessed!) which travels along a 2D grid. You lose by either colliding the head of the snake with another part of its body, or by colliding the head with any of the borders of the grid.

Since the programmer of this version of Snake was lazy, there is not way to grow your snake. In addition to this, the snake will only move when a key is pressed. Your snake will start at the top left of the grid in a straight line touching the top border.

Given a list of keys pressed, will you lose the game?

Input

The first line consists of ~2~ integers ~h, w~ ~(1 \leq h, w \leq 10^8)~, the height and width of the playing grid.

The next line consists of an integer ~l~ ~(1 \leq l \leq \min(10^5, w))~, the length of the snake.

The next line consists of a string ~S~ ~(1 \leq S.\text{length} \leq 10^5)~, the sequence of input keys the user has pressed. The string will only consist of U, D, L and R, representing up, down, left, and right respectively.

Clarifications

• The user will never press an invalid key, like X.
• The user will never make the snake "double-back" on itself. If the snake is travelling downwards, the user will only press D, L, and R, but never U.

Output

Print Snake Wins or Snake Loses depending on the outcome after pressing the keys

Example

Input

4 6
5
DDDLURRRRRR

Output

Snake Loses

Explanation

The snake breaks the rule of colliding with itself before all the moves in the string are complete.

Here is the starting positon of the snake. The H represents the head of the snake, and the numbers are parts of the body that follow the head.

4321H.
......
......
......

After the 3 D moves:

...43.
....2.
....1.
....H.

After the 1 L move:

....4.
....3.
....2.
...H1.

After the 1 U move:

......
....4.
...H3.
...12.

After the next R move, all of the segments will advance one forward, and the the head will be in the same square as the 4 segment, and the game is lost.