Robots#521

Robots

1 seconde
256 mégaoctets
Hard

... Combien de temps avant que Skynet prenne le contrôle de l'humanité ? ...

Il y a un champ qui peut être représenté comme une grille avec lignes et colonnes. Chaque cellule a une direction : droite (R), bas (D), gauche (L), ou haut (U).

Il y a certaines restrictions sur les directions des cellules :

  1. Une cellule ne peut pas pointer en dehors de la grille ;

  2. Chaque cellule a exactement une cellule qui pointe vers elle.

À partir de n'importe quelle cellule, nous pouvons suivre les directions de manière répétée et obtenir une marche : (r_1,c_1),(r_2,c_2),\ldots, où pour chaque i\ge 1, la cellule (r_i,c_i) pointe vers (r_{i+1},c_{i+1}).

Une marche (r_1,c_1),(r_2,c_2),\ldots,(r_k,c_k) est appelée enfermée si :

  1. k \ge 2 ;

  2. (r_1,c_1)=(r_k,c_k) ;

  3. Toutes les cellules (r_1,c_1),(r_2,c_2),\ldots,(r_{k-1},c_{k-1}) sont distinctes par paires.

Une grille est appelée belle si les cellules de la grille peuvent être partitionnées en exactement deux marches enfermées.

Construisez une grille belle, ou déterminez qu'il est impossible de le faire.

Input

La première ligne contient deux entiers et (1 \le n, m \le 100) — la taille de la grille.

Output

Sur la première ligne, affichez "OUI" si le champ existe, et "NON" sinon.

Si la réponse est OUI, sur les lignes suivantes, affichez caractères de {R, D, L, U} — la description de la grille.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Dans le premier exemple, la grille de sortie est :

RRD

ULL

DLL

RRU

Elle peut être représentée comme exactement deux marches enfermées. Par exemple :

  1. (1,1)\to(1,2)\to(1,3)\to(2,3)\to(2,2)\to(2,1)\to(1,1).

  2. (3,1)\to(4,1)\to(4,2)\to(4,3)\to(3,3)\to(3,2)\to(3,1).

Les deux marches enfermées suivent les flèches, sont disjointes, et contiennent ensemble toutes les cellules n \cdot m. Par conséquent, la sortie est valide.

Dans le deuxième exemple, il peut être montré qu'il est impossible de construire une grille belle de 3 \times 3.

Scoring

  1. ( points) n=m=2 ;

  2. ( points) n=m=4 ;

  3. ( points) n=2 ;

  4. ( points) n=4 ;

  5. ( points) et sont tous deux pairs ;

  6. ( points) Pas de restrictions supplémentaires.