리모컨

Jaemin은 무한히 큰 격자 위에 살고 있다. 최근에 새 격자로 이사했기 때문에, 현재 격자에는 벽이 하나뿐이며 이 벽은 한 칸을 차지한다.

각 칸의 좌표는 다음과 같이 정해진다. 벽이 있는 칸의 좌표가 $(0,0)$이다. 어떤 칸의 좌표가 $(x,y)$라면, 바로 오른쪽 칸은 $(x+1,y)$, 바로 왼쪽 칸은 $(x-1,y)$, 바로 위 칸은 $(x,y+1)$, 바로 아래 칸은 $(x,y-1)$이다.

오늘 그는 가장 아끼는 무선 조종 장난감 자동차를 격자에 가져왔다. 자동차는 격자의 한 칸을 정확히 차지한다. 이 격자가 워낙 크기 때문에, 그는 자동차를 어디에 두었는지 잊어버렸다. 이럴 때 자동차를 움직일 수 있는 유일한 방법은 리모컨의 버튼을 누르는 것이다. 버튼을 누르면 자동차는 미리 정해진 $N$번의 이동 경로를 실행하려고 시도하는데, 각 이동에서 자동차는 네 방향 중 하나로 인접한 칸으로 이동하려고 한다. 자동차는 벽으로 들어갈 수 없다. 자동차가 이동하려는 칸에 벽이 있으면, 자동차는 그 명령을 무시하고 움직이지 않지만, 그 뒤의 이동은 계속 실행하려고 한다.

당신이 그를 돕기로 했기 때문에, 그는 다음과 같은 질문을 $Q$번 한다. "내 자동차가 $(x,y)$에서 출발하고 버튼을 한 번 누르면, 어디에서 멈추는가?" 이 질문들에 답할 수 있는가?

첫째 줄에 명령의 길이 $N$이 주어진다. $1 \leq N \leq 300\,000$이다.

다음 줄에 자동차의 미리 정해진 경로가 주어진다. 길이가 $N$인 문자열이며, 각 문자는 L, R, U, D 중 하나이고, 각각 자동차가 왼쪽, 오른쪽, 위, 아래로 이동함을 뜻한다. 그가 버튼을 누르면 자동차는 위에서 설명한 대로 명령의 각 문자를 하나씩 따른다.

다음 줄에 질문의 수 $Q$가 주어진다. $1 \leq Q \leq 300\,000$이다.

다음 $Q$개 줄에 각각 공백으로 구분된 두 정수 $x$와 $y$가 주어진다. 자동차의 출발점은 $(x,y)$이다. 입력은 $-300\,000 \leq x, y \leq 300\,000$을 만족하고, $(x,y) \neq (0,0)$이다.

각 질문에 대해, 질문의 답인 $(x,y)$를 공백으로 구분하여 한 줄에 출력한다.