무지성 로봇청소기

무한한 이차원 격자판에 하나의 로봇청소기가 있다.

일반적인 로봇청소기는 인공지능이 탑재되어 있어 지성을 갖고 청소를 한다. 하지만, 이 로봇청소기는 청소를 시작하면 기존에 탑재된 $N$ 개의 명령어를 무지성으로 차례대로 수행한 후 종료한다.

초기에 로봇청소기는 $(0, 0)$ 칸에 있다.

하나의 명령어는 $(a, b)$의 형태로 나타낼 수 있다. 여기서, $a$는 이동 방향, $b$는 반복 횟수를 의미하며, 명령어는 "$a$ 방향으로 한 칸 이동하는 것을 $b$ 번 반복하라"라는 의미가 있다. $a$는 U, D, R 중 하나이며, 각각 차례대로 위쪽($y$ 좌표가 증가하는 방향), 아래쪽($y$ 좌표가 감소하는 방향), 오른쪽($x$ 좌표가 증가하는 방향)을 뜻한다.

로봇청소기에 탑재된 $i$ 번째 명령어는 $(A_i, B_i)$이다.

여러분은 $(0, 0)$ 칸이 아닌 서로 다른 $N$ 개의 칸에 가구를 설치할 수 있다. 가구가 설치된 칸에는 로봇청소기가 이동할 수 없다. 따라서, 어떤 명령어를 수행하는 로봇청소기가 가구에 의해 더 이동할 수 없다면 그 칸에서 멈추게 되며, 이후의 명령어를 이어서 수행한다.

예를 들어, 세 칸 $(0, 2)$, $(1, -3)$, $(2, 0)$에 가구가 설치되어 있고 $N = 3$ 개의 명령어가 차례대로 (U, $2$), (R, $1$), (D, $3$)라면, 로봇청소기는 $(1, -2)$ 칸에서 청소를 마친다.

청소가 끝난 로봇청소기는 바로 충전을 해주어야 한다. 따라서, 로봇청소기가 청소를 끝마치는 칸과 충전기가 위치하는 칸은 동일해야 한다. 어떤 칸에 충전기를 놓을 수 있도록 하는 가구 배치가 존재하면, 그 칸을 충전 가능 칸이라 부르자.

로봇청소기에 탑재된 $N$ 개의 명령어가 주어질 때, 모든 충전 가능 칸의 개수를 세고, 입력으로 주어지는 칸이 충전 가능 칸인지 판별하는 프로그램을 작성하라.

입력 형식

첫 줄에 명령어의 수와 가구를 설치할 수 있는 칸의 수를 나타내는 정수 $N$이 주어진다. $(1 \le N \le 250\,000)$

그다음 $N$ 개의 줄에 걸쳐 $N$ 개의 명렁어에 대한 정보가 차례대로 주어진다. 이 중 $i$ 번째 줄에 문자 $A_i$와 정수 $B_i$가 공백으로 구분되어 주어진다. $A_i$는 U, D, R 중 하나이며, $1 \le B_i \le 8\,000$이다.

그다음 줄에 충전 가능 칸인지 판별해야 하는 칸의 좌표를 나타내는 두 정수 $X$와 $Y$가 공백으로 구분되어 주어진다. $(|X|, |Y| \le 2\,100\,000\,000)$ 여러분은 $(X, Y)$ 칸이 충전 가능 칸인지 여부를 판별하여야 한다.

출력 형식

첫 줄에 모든 충전 가능 칸의 개수를 출력한다.

만일, $(X, Y)$ 칸이 충전 가능 칸이 아니라면, 둘째 줄에 NO를 출력한다.

$(X, Y)$ 칸이 충전 가능 칸이라면, 둘째 줄에 YES를 출력한다. 이어서, 그다음 줄부터 $N$ 개의 줄에 걸쳐, $(X, Y)$ 칸에 충전기를 놓을 수 있도록 하는 가구 배치를 출력한다. $(x_1, y_1), \cdots, (x_N, y_N)$ 칸에 가구를 배치했을 때 $(X, Y)$ 칸에 충전기를 놓을 수 있다면, 이 중 $i$ 번째 줄에 두 정수 $x_i$, $y_i$를 공백으로 구분하여 출력한다. $(|x_i|, |y_i| \le 2\,100\,000\,000)$

어떤 칸이 충전 가능 칸이면, 위의 조건을 만족하는 가구 배치가 항상 존재함을 증명할 수 있다.

예제 1

3
U 2
R 1
D 1
1 0

7
YES
0 2
2 -1
2 2

예제 2

3
U 2
R 1
D 1
0 2

7
NO

예제 3

2
R 1
R 1
2 0

3
YES
0 1
0 -1

예제 4

8
D 4
R 4
U 6
D 2
R 2
D 1
R 1
U 2
3 -1

103
YES
1 1
3 -2
0 2
2 3
3 1
0 -3
1 -1
3 0

예제 설명

첫 예제에서 충전 가능 칸은 $(0, -1)$, $(0, 0)$, $(0, 1)$, $(1, -1)$, $(1, 0)$, $(1, 1)$, $(1, 2)$로 총 $7$ 개다.

채점 방식

각 데이터에 대해, 충전 가능 칸의 총 개수가 올바르면 $40$%, $(X, Y)$ 칸의 충전 가능 칸 여부와 배치가 올바르면 $60$%의 점수를 얻을 수 있다.

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설