Muchas variantes de rompecabezas tienden a ser más difíciles que sus géneros correspondientes. Pero, paradójicamente, igual que existe una palabra que se vuelve más corta cuando le añades dos letras, existe una variante que hace más fácil cualquier género.
— Freddie Hand
Grammy es una maestra de los rompecabezas. Hoy está jugando a una variante del rompecabezas “Scrabble”: “Easy as Scrabble”.
El rompecabezas consiste en una cuadrícula de $n\times m$. Cada celda debe rellenarse con una letra mayúscula o dejarse vacía.
Hay algunas pistas fuera del rompecabezas. Una pista exterior indica la letra de la primera celda no vacía vista desde esa dirección. Además, algunas celdas pueden contener marcas x, que indican que la celda debe estar vacía.
Por ejemplo, la imagen de la izquierda muestra un rompecabezas sin resolver, y la de la derecha muestra una solución.
Grammy quiere encontrar una solución al rompecabezas. Ayúdala a encontrar una solución o informa de que no existe ninguna.
Entrada
La primera línea contiene 2 enteros $n,m$ ($1\le n,m\le1000$), que indican el número de filas y de columnas de la cuadrícula.
La siguiente línea contiene un punto (.), seguido de $m$ caracteres $U_i$ que indican las pistas sobre la cuadrícula, seguido de un punto (.).
Cada una de las siguientes $n$ líneas contiene una pista $L_i$, seguida de $m$ caracteres $c_{ij}$, seguida de una pista $R_i$, que representan la pista a la izquierda de la cuadrícula, las celdas y la pista a la derecha, respectivamente.
La siguiente línea contiene un punto (.), seguido de $m$ caracteres $D_i$ que indican las pistas debajo de la cuadrícula, seguido de un punto (.).
Cada pista $U_i,L_i,R_i,D_i$ es una letra mayúscula inglesa o un punto (.). Cada celda central $c_{ij}$ es una x o un punto (.).
Todos los puntos de la entrada significan que la posición correspondiente está vacía.
Salida
Si no existe solución, imprime NO en una sola línea.
En caso contrario, imprime YES en la primera línea y después $n$ líneas, cada una con $m$ caracteres, que representen una solución. Cada celda vacía debe representarse con un punto. Si hay varias soluciones, imprime cualquiera.
Ten en cuenta que debes reemplazar por un punto los caracteres x dados en las celdas centrales.
Ten en cuenta también que no debes imprimir las celdas de pistas.
Ejemplos
Entrada 1
5 5 .CBA... ....x.. ..x...C A.....B B..x..A C...... .......
Salida 1
YES CBA.. A.B.C .A.CB BC.A. ..CBA
Entrada 2
1 2 .... Nx.. ..O.
Salida 2
NO