이 문제에는 첨부 파일이 있습니다. 이를 사용하여 로봇의 움직임을 시뮬레이션하고 시각화할 수 있습니다.

VegiCat은 무한한 2차원 격자 위에 로봇을 하나 가지고 있습니다. 그는 로봇을 칸 $s = (s_x, s_y)$에서 칸 $t = (t_x, t_y)$로 이동시키고자 합니다. 각 칸은 정수 좌표를 가집니다. 칸 $s$와 $t$는 같을 수도 있습니다.

로봇은 명령어 문자열 $p$를 따릅니다. 각 문자는 L, R, U, 또는 D입니다. $|p|$를 $p$의 길이라고 합시다.

로봇은 $s$에서 출발합니다. 로봇이 명령을 실행하기 전에, 서로 다른 칸에 최대 $|p|$개의 장애물을 배치할 수 있습니다. 각 장애물의 좌표 $(x, y)$는 $-2 \cdot 10^9 \le x, y \le 2 \cdot 10^9$를 만족해야 합니다. $s$와 $t$에는 장애물을 놓을 수 없습니다. 각 장애물은 한 칸을 차지하며 전체 과정 동안 고정된 상태로 유지됩니다. 다른 모든 칸에는 장애물이 없습니다.

로봇은 명령 $p_1, p_2, \ldots, p_{|p|}$를 순서대로 실행합니다. 각 명령에 대해 현재 칸 $(x, y)$에서 시작하여 다음 칸들의 수열을 따라 이동합니다:

• L: $(x, y) \to (x - 1, y) \to (x - 2, y) \to \cdots$;
• R: $(x, y) \to (x + 1, y) \to (x + 2, y) \to \cdots$;
• U: $(x, y) \to (x, y + 1) \to (x, y + 2) \to \cdots$;
• D: $(x, y) \to (x, y - 1) \to (x, y - 2) \to \cdots$.

로봇은 지정된 방향의 다음 칸에 장애물이 없는 동안 그 방향으로 한 칸씩 반복해서 이동합니다. 그리고 그 방향에서 첫 번째 장애물 바로 앞 칸에 멈춥니다. 명령이 시작되기 전에 지정된 방향의 다음 칸에 이미 장애물이 있다면, 로봇은 제자리에 머무르지만 명령은 완료된 것으로 처리됩니다. 그 방향 앞쪽에 장애물이 없다면 로봇은 영원히 이동하게 되며, 이러한 배치는 유효하지 않습니다.

모든 명령이 완료되기 전에 로봇이 $t$에 도달할 수도 있습니다. 로봇은 남은 모든 명령을 여전히 실행해야 합니다. 마지막 명령 이후에 로봇이 $t$에서 끝나도록 위 요구 사항을 만족하는 장애물 배치를 하나 구성하거나, 그러한 배치가 존재하지 않음을 보고하십시오.

입력

첫 번째 줄에는 테스트 케이스의 개수인 정수 $T$ ($1 \le T \le 10^5$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 시작 칸의 좌표를 나타내는 두 정수 $s_x$와 $s_y$ ($-10^9 \le s_x, s_y \le 10^9$)가 주어집니다.

두 번째 줄에는 목표 칸의 좌표를 나타내는 두 정수 $t_x$와 $t_y$ ($-10^9 \le t_x, t_y \le 10^9$)가 주어집니다.

세 번째 줄에는 문자 L, R, U, D로만 이루어진 명령어 문자열 $p$ ($1 \le |p| \le 10^5$)가 주어집니다.

모든 테스트 케이스에서 $|p|$의 합이 $10^5$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해 입력 순서대로 답을 출력합니다. 서로 다른 테스트 케이스에 대한 장애물 배치는 독립적입니다.

유효한 배치가 존재하지 않으면 한 줄에 NO를 출력합니다.

그렇지 않으면 첫 번째 줄에 YES를 출력합니다. 두 번째 줄에는 장애물의 개수인 정수 $k$ ($0 \le k \le |p|$)를 출력합니다.

그런 다음 $k$개의 줄을 출력합니다. 이 중 $i$번째 줄에는 칸 $(x_i, y_i)$에 놓인 장애물을 지정하는 두 정수 $x_i$와 $y_i$ ($-2 \cdot 10^9 \le x_i, y_i \le 2 \cdot 10^9$)가 포함되어야 합니다.

$k$개의 좌표 쌍은 모두 서로 달라야 하며, 어느 것도 $s$나 $t$와 같아서는 안 됩니다. 배치는 모든 명령이 끝날 수 있게 하고 마지막 명령 이후 로봇을 $t$에 남겨 두어야 합니다. 가능한 해가 여러 개인 경우 아무것이나 출력하십시오.

yes 또는 no 판정은 대소문자에 관계없이 출력할 수 있습니다. 예를 들어 yEs, yes, Yes, YES는 모두 긍정 응답으로 인정됩니다.

예제

입력 1

6
0 0
1 0
RL
0 0
-1 0
URD
0 0
8 0
RLR
0 0
0 0
UDUD
0 0
2 5
RDULR
0 0
1 1
RURURU

출력 1

NO
NO
YES
2
-1 0
9 0
YES
2
0 -1
0 1
YES
5
-1 5
2 -1
2 6
3 0
3 5
YES
3
1 2
2 0
2 1