威斯康星州的春天来了，是该把小奶牛们赶到小牧场上并把大奶牛们赶到北纬 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 次，然后开车去杰克商店办理低脂酸奶的交易和家居装修。
帮助农夫约翰。他必须选择正确的顺序来替换他的奶牛群，使得他从不把一群小奶牛放入当前被同样类型奶牛占有的方格或者当前被同样类型奶牛占据的方格的临近方格。当然，一旦大奶牛走了，小奶牛就被安置好（in place），他必须小心以后的情况，要根据新的排列把奶牛群分开。
非常重要的提示：农夫约翰从过去的经验知道，他必须先移动 D 种奶牛群。
找出农夫约翰将他的小奶牛搬迁到她们的新牧场上的办法。输出 16 个连续的 奶牛群类型/行/列 的信息，使得这样的安排能够符合安全经验。
计算 4 x 4 牧场的最终排列总数和产生那些排列的方式的总数。
格式
PROGRAM NAME: wissqu
INPUT FORMAT
四行，每行四个字母，表示奶牛群。
OUTPUT FORMAT
16 行，每行分别由奶牛群类型/行/列组成。如果有多解（一定有），那么你应该输出奶牛群类型按照字典序排列在最前面的那个解。如果不只一个解满足条件，那么你应该输出行信息按照字典需排列在最前面的那个解。如果仍然不只一个解满足条件，那么你应该输出列信息按照字典序排列在最前面的那个解。
最后多输出一行，包含能够由这个排列方式产生的排列的总数。
SAMPLE INPUT (file wissqu.in)
ABAC
DCDE
BEBC
CADE
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
【参考程序】：
/*
ID: XIONGNA1
PROG: wissqu
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
const int dx[9]={0,1,0,-1,-1,-1,0,1,1};
const int dy[9]={0,1,1,1,0,-1,-1,-1,0};
char ans1[17],a[6][6];
int f[6][6][6],ans2[17],ans3[17],rest[6];
bool done[6][6];
int ans;
void come(int x,int y,char c)
{
for (int i=0;i<=8;i++)
f[x+dx[i]][y+dy[i]][c-64]++;
}
void go(int x,int y,char c)
{
for (int i=0;i<=8;i++)
f[x+dx[i]][y+dy[i]][c-64]--;
}
void Search(int x,int y,int c,int dep)
{
ans1[dep]=c; ans2[dep]=x; ans3[dep]=y;
if (dep==16)
{
ans++;
if (ans==1)
for (int i=1;i<=16;i++)
printf("%c %d %d\n",char(ans1[i]+64),ans2[i],ans3[i]);
return ;
}
go(x,y,a[x][y]);
come(x,y,char(c+64));
done[x][y]=true;
for (int k=1;k<=5;k++)
if (rest[k])
for (int i=1;i<=4;i++)
for (int j=1;j<=4;j++)
if (f[i][j][k]==0 && !done[i][j])
{
rest[k]--;
Search(i,j,k,dep+1);
rest[k]++;
}
come(x,y,a[x][y]);
go(x,y,char(c+64));
done[x][y]=false;
}
int main()
{
freopen("wissqu.in","r",stdin);
freopen("wissqu.out","w",stdout);
memset(f,0,sizeof(f));
for (int i=1;i<=4;i++)
{
for (int j=1;j<=4;j++)
{
scanf("%c",&a[i][j]);
come(i,j,a[i][j]);
}
getchar();
}
memset(done,false,sizeof(done));
ans=0;
for (int i=1;i<=5;i++) rest[i]=3;
for (int i=1;i<=4;i++)
for (int j=1;j<=4;j++)
if (f[i][j][4]==0)
Search(i,j,4,1);
printf("%d\n",ans);
return 0;
}