Walk

Slavko has just tiled his kitchen in a way he finds mathematically interesting. At the start the kitchen is a single tile, a $1 \times 2$ rectangle, as in the picture.

He then split every tile into 4 smaller tiles, and he repeated that $N$ times. After one split the kitchen is a $2 \times 4$ rectangle.

After the second split it is a $4 \times 8$ rectangle.

A split works like this. Every cell breaks into $2 \times 2$ cells, so the area covered by a horizontal tile becomes 2 rows by 4 columns, and 4 new tiles take its place: one vertical tile in the leftmost column, two horizontal tiles in the middle two columns (one in the top row, one in the bottom row), and one vertical tile in the rightmost column. The area covered by a vertical tile becomes 4 rows by 2 columns and gets the same rule turned by 90 degrees: one horizontal tile in the top row, two vertical tiles in the middle two rows (one in the left column, one in the right column), and one horizontal tile in the bottom row.

After the last split you can read the kitchen as a coordinate system in which every tile covers exactly two cells. The cell in the top left corner lies in the first row and the first column and has coordinates $(1, 1)$, and the cell in the bottom right corner has coordinates $(2^N, 2^{N+1})$.

Once the kitchen was tiled, Slavko walked over its cells. He started on cell $(R, S)$ and made a sequence of moves, each one to one of the 4 cells next to the current one. The moves are written with these characters:

• 'L' is a move to the neighbouring cell on the left.
• 'R' is a move to the neighbouring cell on the right.
• 'U' is a move to the neighbouring cell above.
• 'D' is a move to the neighbouring cell below.

For every move Slavko makes, decide whether he crossed from one tile to another.

The first line contains an integer $N$ ($0 \le N \le 20$).

The second line contains two integers $R$ and $S$ ($1 \le R \le 2^N$, $1 \le S \le 2^{N+1}$), the row and the column of the cell where Slavko starts.

The third line contains the string of Slavko's moves, written with the characters 'L', 'R', 'D' and 'U'. The string is at most 100,000 characters long. Slavko never makes a move that leaves the rectangle.

Print one line with a string whose $i$-th character is 'Y' if Slavko crossed from one tile to another with his $i$-th move, and 'N' if he stayed on the same tile.

In the first example Slavko's path looks like this.

The black arrows are the moves where Slavko crossed from one tile to another.