Petryk and Snake

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Petryk and the Little Elephant are playing a computer game called "Snake". The game takes place on an infinite plane and works as follows: initially, the coordinates \(x\), \(y\) of the snake’s head are given. The game lasts for \(n\) turns: on each turn, a direction is chosen in which the snake’s head will move next. The tail and body of the snake remain stationary, meaning that after each valid move, the length of the snake increases by 1. The game ends successfully if all \(n\) turns are completed, and the snake’s head never collides with the snake’s body.

For the initial coordinates \(x\), \(y\) chosen by Petryk and the sequence of moves chosen by the Little Elephant, you need to answer whether the game will end successfully. In case the game ends unsuccessfully, output the turn number after which the first collision of the snake’s head with its body occurs.

Input

The first line gives \(x\), \(y\) — the initial coordinates of the snake.

The second line gives the string \(s\), which defines the sequence of moves. The string \(s\) consists only of the characters L, R, U, D. If the snake’s head is at the point with coordinates \((x, y)\), then in case of the command L it will move to the point \((x - 1, y)\), R — to the point \((x + 1, y)\), U — to the point \((x, y + 1)\), D — to the point \((x, y - 1)\).

Output

Output Success if the game ends successfully. Otherwise, in the first line output Fail, and in the second line output the turn number after which the first collision of the snake’s head with its body occurs. Turns are numbered starting from one.

Constraints

\(1 \le x, y \le 10^5\),

30% of tests: \(1 \le |s| \le 10^3\),

70% of tests: \(10^3 \le |s| \le 10^6\), where \(|s|\) is the length of the string \(s\).

Samples