산책

슬라브코는 수학적으로 흥미로운 방식으로 부엌 바닥에 타일을 깔았다. 처음에 부엌은 다음 그림처럼 $1 \times 2$ 직사각형 타일 한 장이다.

여기서 슬라브코는 모든 타일을 더 작은 타일 4장으로 쪼개는 작업을 $N$번 반복했다. 한 번 쪼개면 $2 \times 4$ 직사각형이 된다.

두 번 쪼개면 $4 \times 8$ 직사각형이 된다.

쪼개는 규칙은 다음과 같다. 쪼갤 때마다 칸 하나가 $2 \times 2$ 칸으로 갈라지므로, 가로 타일이 덮고 있던 영역은 2행 4열이 되고 그 자리에 타일 4장이 들어간다. 맨 왼쪽 열에 세로 타일 한 장, 가운데 두 열에 가로 타일 두 장(위쪽 행에 한 장, 아래쪽 행에 한 장), 맨 오른쪽 열에 세로 타일 한 장이다. 세로 타일이 덮고 있던 영역은 4행 2열이 되고, 같은 규칙을 90도 돌려서 적용한다. 맨 위 행에 가로 타일 한 장, 가운데 두 행에 세로 타일 두 장(왼쪽 열에 한 장, 오른쪽 열에 한 장), 맨 아래 행에 가로 타일 한 장이다.

마지막까지 쪼개고 나면 부엌을 좌표계로 볼 수 있고, 타일 한 장은 정확히 두 칸을 덮는다. 왼쪽 위 칸은 첫째 행 첫째 열에 있고 좌표가 $(1, 1)$이며, 오른쪽 아래 칸의 좌표는 $(2^N, 2^{N+1})$이다.

타일을 다 깐 뒤 슬라브코는 시작 칸 $(R, S)$에서 출발해, 지금 서 있는 칸과 인접한 네 칸 중 하나로 옮겨 가는 이동을 차례로 하며 부엌을 걸어 다녔다. 이동은 다음 문자로 나타낸다.

• 'L'은 왼쪽 인접한 칸으로 가는 이동이다.
• 'R'는 오른쪽 인접한 칸으로 가는 이동이다.
• 'U'는 위쪽 인접한 칸으로 가는 이동이다.
• 'D'는 아래쪽 인접한 칸으로 가는 이동이다.

슬라브코가 이동할 때마다 두 타일 사이를 넘어갔는지 판정하라.

첫째 줄에 정수 $N$이 주어진다 ($0 \le N \le 20$).

둘째 줄에 슬라브코가 처음 서 있는 칸의 행과 열을 나타내는 정수 $R$, $S$가 주어진다 ($1 \le R \le 2^N$, $1 \le S \le 2^{N+1}$).

셋째 줄에 슬라브코의 이동을 나타내는 문자열이 주어진다. 이 문자열은 'L', 'R', 'D', 'U'로 이루어지고 길이는 100,000자를 넘지 않는다. 슬라브코는 직사각형 밖으로 나가는 이동을 하지 않는다.

한 줄에 문자열을 출력한다. $i$번째 문자는 슬라브코가 $i$번째 이동으로 두 타일 사이를 넘어갔으면 'Y', 같은 타일에 머물렀으면 'N'이다.

첫 번째 예제에서 슬라브코의 경로는 다음과 같다.

검게 칠한 화살표가 슬라브코가 두 타일 사이를 넘어간 이동이다.