在加载游戏“地下城与糖果”期间,您需要从服务器获取 k 个关卡的描述。每个描述都是一个 n × m 方格矩形区域的地图。场地中的某些单元格包含糖果(每个单元格最多有一颗糖果)。空单元格表示为“.”。在地图上,但如果一个单元格有糖果,它就会被表示为英文字母表中的字母。一个关卡可能包含相同的糖果,在这种情况下,地图相应单元格中的字母将相同。
当您通过网络传输信息时,您希望最小化流量——传输数据的总大小。电平可以按任何顺序传输。传输当前电平A有两种方式:
1、可以传输整个A级,那么需要通过网络传输n·m个字节。
2.您可以传输级别A与某些先前传输的级别B之间的差异(如果存在);该操作需要传输dA, B·w字节,其中dA, B是A和B不同的字段单元数,w是常数。请注意,您应该仅比较级别 A 和 B 的相应单元格来计算 dA, B。您不能变换级别的地图,即旋转或相对于彼此移动它们。
你的任务是找到一种方法来传输所有 k 个级别并最小化流量。
输入
第一行包含四个整数 n、m、k、w(1 ≤ n,m ≤ 10;1 ≤ k,w ≤ 1000)。接下来是k个级别的描述。每个级别由n行描述,每行包含m个字符。每个字符可以是英文字母表中的字母或点(“.”)。请注意字母的大小写很重要。
输出
在第一行中打印所需的最小传输字节数。
然后打印k对整数x1, y1, x2, y2, ..., xk, yk,描述转移级别的方式。 xi,yi 配对表示xi 层需要通过yi 方式转移。如果 yi 等于 0,则表示该级别必须使用第一种方式转移,否则 yi 必须等于先前转移的级别号。这意味着您将传递 yi 级和 xi 级之间的差值来传递 xi 级。按照传输级别的顺序打印对。级别按照它们在输入中遵循的顺序编号为 1 到 k。
如果有多个最优解,可以打印任意一个。
示例
输入 #1
2 3 3 2 A.A ... A.a ..C X.Y ...
输出 #1
14 1 0 2 1 3 1
输入 #2
1 1 4 1 A . B .
输出 #2
3 1 0 2 0 4 2 3 0
输入 #3
1 3 5 2 ABA BBB BBA BAB ABB
输出 #3
11 1 0 3 1 2 3 4 2 5 1