К этой задаче прикреплён файл. Вы можете использовать его для симуляции и визуализации движений робота.

У VegiCat есть робот на бесконечной двумерной сетке. Он хочет переместить его из клетки $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$) — координаты целевой клетки.

Третья строка содержит строку инструкций $p$ ($1 \le |p| \le 10^5$), состоящую только из символов L, R, U и D.

Гарантируется, что сумма $|p|$ по всем наборам входных данных не превосходит $10^5$.

Выходные данные

Для каждого набора входных данных выведите ответ в порядке следования во входных данных. Размещения препятствий для разных наборов входных данных независимы.

Если корректного размещения не существует, выведите NO в отдельной строке.

В противном случае выведите YES в первой строке. Во второй строке выведите целое число $k$ ($0 \le k \le |p|$) — количество препятствий.

Затем выведите $k$ строк. $i$-я из этих строк должна содержать два целых числа $x_i$ и $y_i$ ($-2 \cdot 10^9 \le x_i, y_i \le 2 \cdot 10^9$), задающих препятствие в клетке $(x_i, y_i)$.

Все $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