さまざまな活動の文書、小冊子、ステッカーを印刷する International Collaborative Printing Company (ICPC) で働いています。会社は最近、新しいステッカー印刷機を購入しました。この機械は設定された三角形の模様を大きな用紙に印刷します。用紙は $M$ 行 $N$ 列の $M\times N$ の格子です。各マスは指定された方法で2つの三角形に分けられ、その一部がインクで塗られます。図8に例を示します。
図8：個々のステッカーに切り分ける前の印刷済み用紙。
各ステッカーは比較的小さいので、1枚の用紙に複数を印刷してから切り離します。三角形の境界に沿って切れますが、品質を保つため、塗られた三角形の辺に沿って切ってはいけません。小さく切り分けた後、塗られた三角形がない部分は捨てます。残るステッカーには少なくとも1つの塗られた三角形があり、各ステッカー内の塗られた三角形はすべて連結です。つまり任意の2つの間には同じステッカー内の塗られた三角形の列があり、隣接する各組が少なくとも1点を共有します。図9に有効な切り方と無効な切り方を示します。
図9：一番左のステッカーは有効ですが、他の2つは無効です。
すべてを切り離した後、各ステッカーの境界を磨きます。穴がある場合もあり（入力例2）、穴の境界も磨く必要があります。切断は無料ですが、研磨には費用がかかります。境界は水平、垂直、斜めの切断に対応する線分の集合で表されます。水平線分の研磨費用は $H$、垂直線分は $V$ です。斜めの切断の費用 $\{D_{ij}\}$ は位置によって異なり、$i$ 行 $j$ 列では $D_{ij}$ です。ステッカーの研磨費用はすべての境界線分の費用の合計です。図10と図11を参照してください。
各ステッカーを切り離して磨く最小費用を求めるプログラムを書いてください。すべてのステッカーを一度に切り離し、各ステッカーが同時に最小研磨費用を達成する最適な切り方が存在すると証明できます。
図10：研磨費用の計算例。$H=V=10$、各斜めの切断の費用を $D_{ij}=1$ とします。左のステッカーは水平4線分、垂直4線分、斜め6線分からなり、合計費用は86です。右の費用は106です。
図11：入力例2の図。穴の境界も研磨が必要です。各ステッカーの費用はそれぞれ723、196、214です。
入力
1行目にはテストケース数の整数 $T$ があります。各ケースの最初の行には整数 $M,N,H,V$ があり、それぞれ行数、列数、水平線分と垂直線分の研磨費用です。続く $M$ 行には長さ $N$ の文字列があり、各文字は / または \ です。$i$ 番目の文字列の $j$ 番目の文字は対角線の向きを表します。さらに $M$ 行の長さ $2N$ の文字列が続きます。マス $(i,j)$ では、$i$ 番目の文字列の $(2j+1)$ 番目の文字が対角線の左側の三角形、$(2j+2)$ 番目が右側の三角形が塗られているかを表します。塗られていれば #、そうでなければ . です。最後に $M$ 行があり、$i$ 行目の $N$ 整数 $D_{i1},D_{i2},\ldots,D_{iN}$ は各対角線の研磨費用です。
制約
$1\le T\le50$。
$M\ge2$; $N\ge2$; $4\le M\times N\le10000$。
すべての $1\le i\le M$, $1\le j\le N$ に対して $1\le H,V,D_{ij}\le1000$。
各ケースで機械は1個以上1000個以下のステッカーを作ります。
用紙全体の境界に辺がある塗られた三角形はありません。
出力
各ケースにつき2行出力します。1行目にはステッカーの総数 $k$ を出力します。2行目には各ステッカーの最小研磨費用を表す $k$ 整数 $c_1,c_2,\ldots,c_k$ を非減少順に出力します。
入出力例
入力 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
出力 1
2 86 106
入力 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
出力 2
3 196 214 723