여러 행사에 필요한 문서, 소책자, 스티커를 인쇄하는 International Collaborative Printing Company (ICPC)에서 일하고 있다. 회사는 최근 새 스티커 인쇄기를 구입했다. 이 기계는 미리 설정된 삼각형 무늬를 큰 스티커 용지에 인쇄한다. 용지는 $M$행 $N$열인 $M\times N$ 격자이다. 각 칸은 지정된 방식으로 두 삼각형으로 나뉘고 기계는 일부 삼각형을 잉크로 채운다. 그림 8을 참고하라.
그림 8: 개별 스티커로 자르기 전의 인쇄된 스티커 용지.
각 스티커는 비교적 작으므로 한 용지에 여러 개를 인쇄한 뒤 잘라낸다. 삼각형의 경계를 따라 자를 수 있지만 품질을 위해 잉크로 채운 삼각형의 변을 따라서는 자르면 안 된다. 용지를 여러 작은 조각으로 나눈 뒤 채운 삼각형이 없는 조각은 버린다. 남은 스티커에는 적어도 하나의 채운 삼각형이 있어야 하며, 각 스티커의 모든 채운 삼각형은 연결되어 있다. 즉, 임의의 두 채운 삼각형 사이에 같은 스티커의 채운 삼각형들로 이루어진 순서열이 있고, 이웃한 두 삼각형은 적어도 한 공통점을 공유한다. 그림 9는 올바른 절단과 잘못된 절단을 보여준다.
그림 9: 가장 왼쪽 스티커는 올바르지만 나머지 둘은 올바르지 않다.
모든 스티커를 잘라낸 뒤 각각의 경계를 다듬는다. 스티커에는 구멍이 있을 수 있으며(예제 입력 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이다.
입력
첫 줄에는 테스트 케이스 수인 정수 $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개의 스티커를 만든다.
전체 용지의 경계에 변이 놓인 채운 삼각형은 없다.
출력
각 테스트 케이스마다 두 줄을 출력한다. 첫 줄의 정수 $k$는 스티커의 총 개수이다. 둘째 줄에는 모든 스티커의 최소 다듬기 비용을 나타내는 $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