Ce problème comporte une pièce jointe. Vous pouvez l'utiliser pour simuler et visualiser les déplacements du robot.

VegiCat possède un robot sur une grille bidimensionnelle infinie. Il souhaite le faire aller de la case $s = (s_x, s_y)$ à la case $t = (t_x, t_y)$. Chaque case a des coordonnées entières. Les cases $s$ et $t$ peuvent être identiques.

Le robot suit une chaîne d'instructions $p$. Chaque caractère est L, R, U ou D. Soit $|p|$ la longueur de $p$.

Le robot commence en $s$. Avant qu'il n'exécute la moindre instruction, vous pouvez placer au plus $|p|$ obstacles dans des cases distinctes. Les coordonnées $(x, y)$ de chaque obstacle doivent vérifier $-2 \cdot 10^9 \le x, y \le 2 \cdot 10^9$. Ni $s$ ni $t$ ne peuvent contenir d'obstacle. Chaque obstacle occupe une case et reste fixe tout au long du processus ; toutes les autres cases sont libres d'obstacles.

Le robot exécute les instructions $p_1, p_2, \ldots, p_{|p|}$ dans l'ordre. Pour chaque instruction, en partant de sa case actuelle $(x, y)$, il se déplace le long de la séquence de cases suivante :

• 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$.

Le robot avance de façon répétée d'une case dans la direction indiquée tant que la case suivante ne contient pas d'obstacle. Il s'arrête dans la case située immédiatement avant le premier obstacle dans cette direction. Si la case suivante dans la direction indiquée contient déjà un obstacle avant le début de l'instruction, le robot reste sur place, mais l'instruction est tout de même terminée. S'il n'y a aucun obstacle devant lui dans cette direction, le robot se déplacerait indéfiniment, et le placement est invalide.

Le robot peut atteindre $t$ avant que toutes les instructions ne soient terminées. Il doit tout de même exécuter toutes les instructions restantes. Construisez n'importe quel placement d'obstacles satisfaisant les conditions ci-dessus tel que le robot termine en $t$ après la dernière instruction, ou indiquez qu'aucun tel placement n'existe.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^5$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $s_x$ et $s_y$ ($-10^9 \le s_x, s_y \le 10^9$), les coordonnées de la case de départ.

La deuxième ligne contient deux entiers $t_x$ et $t_y$ ($-10^9 \le t_x, t_y \le 10^9$), les coordonnées de la case cible.

La troisième ligne contient la chaîne d'instructions $p$ ($1 \le |p| \le 10^5$), constituée uniquement des caractères L, R, U et D.

Il est garanti que la somme de $|p|$ sur l'ensemble des cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez une réponse dans l'ordre de l'entrée. Les placements d'obstacles pour différents cas de test sont indépendants.

S'il n'existe aucun placement valide, affichez NO seul sur une ligne.

Sinon, affichez YES sur la première ligne. Sur la deuxième ligne, affichez un entier $k$ ($0 \le k \le |p|$), le nombre d'obstacles.

Affichez ensuite $k$ lignes. La $i$-ème de ces lignes doit contenir deux entiers $x_i$ et $y_i$ ($-2 \cdot 10^9 \le x_i, y_i \le 2 \cdot 10^9$), indiquant un obstacle dans la case $(x_i, y_i)$.

Les $k$ couples de coordonnées doivent tous être distincts, et aucun ne peut être égal à $s$ ou $t$. Le placement doit permettre à chaque instruction de se terminer et laisser le robot en $t$ après la dernière instruction. S'il existe plusieurs solutions, affichez n'importe laquelle d'entre elles.

Vous pouvez afficher le verdict yes ou no dans n'importe quelle casse. Par exemple, yEs, yes, Yes et YES sont tous acceptés comme réponses positives.

Exemples

Entrée 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

Sortie 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