你所在的国际协作印刷公司（ICPC）负责印刷各种文档、小册子和贴纸。最近，公司购入了一台新的贴纸印刷机。这台印刷机可以在巨大的贴纸纸张上印刷预设的三角形图案。纸张可以描述为一个 $M \times N$ 的网格，其中 $M$ 是行数，$N$ 是列数。每个单元格以某种指定方式被划分为两个三角形，机器会在其中一些三角形中填充墨水。如图 8 所示。
图 8：切割成单个贴纸前的印刷贴纸纸张。
由于每张贴纸都比较小，打印机会在一张纸上印刷多张贴纸，然后将它们从纸上切割下来。切割可以沿着三角形的边界进行。然而，为了确保贴纸的高质量，要求所有切割线都不能穿过任何已填充三角形的边缘。注意，将贴纸纸张切割成许多小块后，没有填充三角形的碎片会被丢弃。剩下的每张贴纸至少包含一个已填充的三角形。此外，在每张贴纸上，所有已填充的三角形都是连通的。也就是说，对于任意两个已填充的三角形，在同一张贴纸上都存在一个已填充三角形序列，使得每一对相邻的三角形至少共享一个公共点。图 9 展示了切割贴纸纸张的有效和无效方式。
图 9：最左侧的贴纸是有效的，而另外两个贴纸是无效的。
在将所有贴纸从纸张上切割下来后，会对每张贴纸的边界进行额外的抛光处理。注意，贴纸可能会有孔（参见样例输入 2）。在这种情况下，孔的边界也需要进行抛光。切割纸张是免费的，但抛光步骤会产生一定的成本。具体来说，每张贴纸的边界可以描述为一系列线段的集合。每条线段指的是水平切割、垂直切割或对角线切割。每次水平切割的抛光成本为 $H$，每次垂直切割的抛光成本为 $V$。对角线切割的抛光成本 $\{D_{ij}\}$ 略有不同，取决于切割的位置。具体而言，第 $i$ 行第 $j$ 列的对角线切割的抛光成本为 $D_{ij}$。贴纸的抛光成本定义为与该贴纸边界相关的所有线段的抛光成本之和。参见图 10 和图 11。
请编写一个程序，帮助公司计算每张贴纸切割并抛光的最小成本。可以证明，存在一种最优方法可以一次性将所有贴纸从纸张上切割下来，使得每张贴纸同时达到最小抛光成本。
输入格式
第一行包含一个整数 $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}, \dots, D_{iN}$，表示每条对角线的抛光成本。
数据范围
- $1 \le T \le 50$。
- $M \ge 2; N \ge 2; 4 \le M \times N \le 10,000$。
- 对于所有 $1 \le i \le M$ 和 $1 \le j \le N$，有 $1 \le H, V, D_{ij} \le 1,000$。
- 对于每个测试用例，机器至少产生 1 张贴纸，最多产生 1,000 张贴纸。
- 不存在任何已填充三角形的边缘位于整个贴纸纸张的边界上。
输出格式
每个测试用例输出两行。第一行包含一个整数 $k$，表示贴纸的总数。第二行包含 $k$ 个整数 $c_1, c_2, \dots, 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
说明
图 10：计算贴纸抛光成本的示例。假设 $H = V = 10$，且每条对角线切割的成本 $D_{ij} = 1$。左侧的第一张贴纸由 4 条水平线段、4 条垂直线段和 6 条对角线段组成，因此总成本为 86。右侧的第二张贴纸成本为 106。
图 11：样例输入 2 的说明。注意孔的边界也需要抛光。每张贴纸的抛光成本分别为 723、196 和 214。