10523 - 威斯康星州的牧场

威斯康星州的春天来了，是该把小奶牛们赶到小牧场上并把大奶牛们赶到北纬 40 度的大牧场上的时候了。

农夫约翰的牧场上有五种奶牛（括号内的是缩写）：格恩西奶牛（A），泽西奶牛（B），赫里福奶牛（C），黑安格斯奶牛（D），朗赫恩奶牛（E）。这些奶牛 群放养在一片 16 英亩的牧场上，每英亩上都有一小群奶牛，像下面这样排列成 4 x 4 的格子（用行和列标号）：

1 2 3 4 +------- 1|A B A C 2|D C D E 3|B E B C 4|C A D E

最初，牧场上的奶牛群总共有 3 群 A，3 群 B，4 群 C，3 群 D，3 群 E。今年的 D 种小奶牛比去年多一群 ，C 种少一群，共有 3 群 A，3 群 B，3 群 C，4 群 D，3 群 E。

农夫约翰对于他牧场上的奶牛群的布局非常小心。这是因为如果同一种类型的奶牛群靠得太近，她们就乱来：她们聚集在栅栏边上抽烟，喝牛奶。如果她们在相同的格子上或者在临近的 8 个格子上，就是靠得太近了。

农夫约翰得用他的棕色旧福特皮卡把他的大奶牛群运出牧场，并把他的小奶牛群运进牧场，皮卡一次只能运一群奶牛。他装上一群小奶牛，开车到小牧场的一个方格 中，卸下这群小奶牛，再装上这个格子上的那群大奶牛，开到北纬 40 度的大牧场卸下来。他重复这样的操作 16 次，然后开车去杰克商店办理低脂酸奶的交易和家居装修。

帮助农夫约翰。他必须选择正确的顺序来替换他的奶牛群，使得他从不把一群小奶牛放入当前被同样类型奶牛占有的方格或者当前被同样类型奶牛占据的方格的临近方格。当然，一旦大奶牛走了，小奶牛来了，他必须小心以后的情况，要根据新的排列把奶牛群分开。

非常重要的提示：农夫约翰从过去的经验知道，他必须先移动 D 种奶牛群。

找出农夫约翰将他的小奶牛搬迁到她们的新牧场上的办法。输出 16 个连续的 奶牛群类型/行/列 的信息，使得这样的安排能够符合安全经验。

计算 4 x 4 牧场的最终排列总数（这应该是原题作者的笔误，输出样例中并没有说明要输出最终排列总数，此题只有一个测试数据，也没有体现这个问题——译者注），和产生那些排列的方式的总数。

四行，每行四个用空格分开的字母，表示奶牛群（又是原题作者的笔误了，字母之间没有空格——译者注）。

16 行，每行分别由 奶牛群类型/行/列 组成。如果有多解（一定有），那么你应该输出奶牛群类型按照字典序排列在最前面的那个解。如果不只一个解满足条件，那么你应该输出行信息按照字典需排列在 最前面的那个解。如果仍然不只一个解满足条件，那么你应该输出列信息按照字典序排列在最前面的那个解。

最后多输出一行，包含能够由这个排列方式产生的排列的总数。

Wisconsin Squares

It's spring in Wisconsin and time to move the yearling calves to the yearling pasture and last year's yearlings to the greener pastures of the north 40.

Farmer John has five kinds of cows on his farm (abbreviations are shown in parentheses): Guernseys (A), Jerseys (B), Herefords (C), Black Angus (D), and Longhorns (E). These herds are arranged on the 16 acre pasture, one acre for each small herd, on a 4 x 4 grid (labeled with rows and columns) like this:

          1 2 3 4
         +-------
        1|A B A C
        2|D C D E
        3|B E B C
        4|C A D E

In the initial pasture layout, the herds total 3 A's, 3 B's, 4 C's, 3 D's, and 3 E's. This year's calves have one more D herd and one fewer C herd, for a total of 3 A's, 3 B's, 3 C's, 4 D's, and 3 E's.

FJ is extremely careful in his placement of herds onto his pasture grid. This is because when herds of the same types of cows are too close together, they misbehave: they gather near the fence and smoke cigarettes and drink milk. Herds are too close together when they are on the same square or in any of the eight adjacent squares.

Farmer John must move his old herd out of the field and his new herd into the field using his old brown Ford pickup truck, which holds one small herd at a time. He picks up a new herd, drives to a square in the yearling pasture, unloads the new herd, loads up the old herd, and drives the old herd to the north 40 where he unloads it. He repeats this operation 16 times and then drives to Zack's for low-fat yogurt treats and familiar wall decor.

Help Farmer John. He must choose just exactly the correct order to replace the herds so that he never puts a new herd in a square currently occupied by the same type of herd or adjacent to a square occupied by the same type of herd. Of course, once the old cows are gone and the new cows are in place, he must be careful in the future to separate herds based on the new arrangement.

Very important hint: Farmer John knows from past experience that he must move a herd of D cows first.

Find a way for Farmer John to move the yearlings to their new pasture. Print the 16 sequential herd-type/row/column movements that lead to a safe moving experience for the cows.

Calculate the total number of possible final arrangements for the 4x4 pasture and calculate the total number of ways those arrangements can be created.

PROGRAM NAME: wissqu INPUT FORMAT Four lines, each with four letters that denote herds.

SAMPLE INPUT (file wissqu.in) ABAC DCDE BEBC CADE

OUTPUT FORMAT 16 lines, each with a herd-type, row and column. If there are multiple solutions (and there are), you should output the solution for which the string of herd-types is first in lexicografic order. If tied, you should output the solution for which the string of the rows is first in lexicographic order. If still tied, you should output the solution for which the string of the columns is first in lexicografic order.

One more line with the total number of ways these arrangements can be created.

SAMPLE OUTPUT (file wissqu.out) D 4 1 C 4 2 A 3 1 A 3 3 B 2 4 B 3 2 B 4 4 E 2 1 E 2 3 D 1 4 D 2 2 C 1 1 C 1 3 A 1 2 E 4 3 D 3 4 14925