Trabajas en International Collaborative Printing Company (ICPC), que imprime documentos, folletos y pegatinas para todo tipo de campañas. La empresa acaba de adquirir una nueva impresora de pegatinas. Imprime patrones triangulares preconfigurados en una gran hoja. La hoja es una cuadrícula de $M\times N$ celdas, donde $M$ es el número de filas y $N$ el de columnas. Cada celda se divide de una forma especificada en dos triángulos y la máquina rellena algunos con tinta. La figura 8 muestra un ejemplo.
Figura 8: Una hoja impresa antes de cortarla en pegatinas individuales.
Como cada pegatina es pequeña, se imprimen varias en una hoja y después se recortan. Los cortes pueden seguir los bordes de los triángulos, pero para garantizar la calidad no deben seguir ningún lado de un triángulo relleno. Tras dividir la hoja en piezas pequeñas, se descartan las que no tienen triángulos rellenos. Cada pegatina restante tiene al menos uno. Además, todos sus triángulos rellenos están conectados: para cualesquiera dos hay una secuencia de triángulos rellenos de la misma pegatina en la que cada pareja consecutiva comparte al menos un punto. La figura 9 muestra cortes válidos e inválidos.
Figura 9: La pegatina de la izquierda es válida, pero las otras dos son inválidas.
Después de recortar todas las pegatinas, se pule el borde de cada una. Una pegatina puede tener agujeros (véase la entrada de ejemplo 2); sus bordes también deben pulirse. Cortar es gratis, pero pulir tiene costes. El borde se describe mediante segmentos horizontales, verticales o diagonales. Cada segmento horizontal tiene coste de pulido $H$ y cada vertical $V$. Los costes diagonales $\{D_{ij}\}$ dependen de la posición: la diagonal de la fila $i$ y columna $j$ cuesta $D_{ij}$. El coste de pulir una pegatina es la suma de los costes de todos sus segmentos. Véanse las figuras 10 y 11.
Escribe un programa que calcule para cada pegatina el coste mínimo de cortarla y pulirla. Se puede demostrar que existe una forma óptima de recortar todas las pegatinas a la vez de modo que todas alcancen simultáneamente su coste mínimo de pulido.
Figura 10: Cálculo del coste de pulido. Supón $H=V=10$ y $D_{ij}=1$ para cada diagonal. La pegatina izquierda tiene 4 segmentos horizontales, 4 verticales y 6 diagonales, por lo que cuesta 86. La derecha cuesta 106.
Figura 11: Ilustración de la entrada de ejemplo 2. También se pulen los bordes de los agujeros. Los costes son 723, 196 y 214, respectivamente.
Entrada
La primera línea contiene un entero $T$, el número de casos de prueba. La primera línea de cada caso contiene $M,N,H,V$: las filas, las columnas y los costes por segmento horizontal y vertical. Las siguientes $M$ líneas contienen cadenas de longitud $N$ cuyos caracteres son / o \. El $j$-ésimo carácter de la $i$-ésima cadena indica la dirección de la diagonal. Siguen otras $M$ líneas, cada una con una cadena de longitud $2N$. Para la celda $(i,j)$, el carácter $(2j+1)$ de la $i$-ésima cadena indica si el triángulo izquierdo está relleno y el $(2j+2)$ si lo está el derecho. Un triángulo relleno se representa con #; de lo contrario, con .. Finalmente hay $M$ líneas; la $i$-ésima contiene $N$ enteros $D_{i1},D_{i2},\ldots,D_{iN}$, los costes de pulir las diagonales.
Restricciones
$1\le T\le50$.
$M\ge2$; $N\ge2$; $4\le M\times N\le10000$.
$1\le H,V,D_{ij}\le1000$ para todo $1\le i\le M$ y $1\le j\le N$.
En cada caso se producen al menos 1 y como máximo 1000 pegatinas.
Ningún triángulo relleno tiene un lado en el borde de toda la hoja.
Salida
Cada caso produce dos líneas. La primera contiene un entero $k$, el número total de pegatinas. La segunda contiene $k$ enteros $c_1,c_2,\ldots,c_k$, los costes mínimos de pulido de todas las pegatinas, ordenados de forma no decreciente.
Ejemplos
Entrada 1
1 4 9 10 10 \////\\/\ \\/\//\// //\\/\\/\ \///\//\/ .....#...##....... .##.#.....##...##. ...#.##....####... ..#.........#..##. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Salida 1
2 86 106
Entrada 2
1 8 12 20 19 \//\//\/\\\/ //\/\\\///// ///\/\\\\//\ \//\\\/\/\/\ \\\\\///\/// ///\\\\\\\\\ //\/////\\\\ /////\////// ........................ ..##################.... ..##..............##.... ..##..######....##...... ..##..##......####..##.. ..##........##......##.. ..############....####.. ........................ 11 12 13 15 14 12 17 16 14 13 11 10 12 13 15 14 13 17 18 17 15 14 12 16 16 17 18 17 15 14 13 11 16 17 18 19 19 11 12 13 15 14 16 16 17 18 14 13 13 20 16 15 14 14 13 11 10 12 12 13 16 17 17 14 15 16 19 12 14 11 14 16 18 17 14 14 16 19 18 14 15 13 12 14 15 16 17 15 11 18 19 16 16 14 14 20
Salida 2
3 196 214 723