001 #include<cstdlib>
002 #include<fstream>
003 #include<iterator>
004 #include<algorithm>
005 using namespace std;
006
007 class farm{
008     int cnt, cowat[16], cowleft[5];
009     bool nochange[16];
010     unsigned long long ajtcnt[5];
011     const unsigned long long mask, maskl, maskr;
012     pair<int, int> putorder[16];
013     int dfscow[16], dfspos[16];
014
015     void addcow(int cowidx, int posidx){
016         switch(posidx){
017             /*
018                 0  1  2  3
019                 4  5  6  7
020                 8  9 10 11
021                12 13 14 15
022             */
023             case 0:
024             case 4:
025                 ajtcnt[cowidx] += maskl >> (5 - posidx) * 4;
026                 break;
027             case 3:
028                 ajtcnt[cowidx] += maskr >> (5 - posidx) * 4;
029                 break;
030             case 1:
031             case 2:
032                 ajtcnt[cowidx] += mask >> (5 - posidx) * 4;
033                 break;
034             case 5:
035             case 6:
036             case 9:
037             case 10:
038             case 13:
039             case 14:
040                 ajtcnt[cowidx] += mask << (posidx - 5) * 4;
041                 break;
042             case 8:
043             case 12:
044                 ajtcnt[cowidx] += maskl << (posidx - 5) * 4;
045                 break;
046             case 7:
047             case 11:
048             case 15:
049                 ajtcnt[cowidx] += maskr << (posidx - 5) * 4;
050                 break;
051         }
052         cowat[posidx] = cowidx;
053     }
054     int replace(int newcow, int posidx){
055         int oldcow = cowat[posidx];
056         unsigned long long m;
057         switch(posidx){
058             case 0:
059             case 4:
060                 m = maskl >> (5 - posidx) * 4;
061                 ajtcnt[newcow] += m;
062                 ajtcnt[oldcow] -= m;
063                 break;
064             case 3:
065                 m = maskr >> (5 - posidx) * 4;
066                 ajtcnt[newcow] += m;
067                 ajtcnt[oldcow] -= m;
068                 break;
069             case 1:
070             case 2:
071                 m = mask >> (5 - posidx) * 4;
072                 ajtcnt[newcow] += m;
073                 ajtcnt[oldcow] -= m;
074                 break;
075             case 5:
076             case 6:
077             case 9:
078             case 10:
079             case 13:
080             case 14:
081                 m = mask << (posidx - 5) * 4;
082                 ajtcnt[newcow] += m;
083                 ajtcnt[oldcow] -= m;
084                 break;
085             case 8:
086             case 12:
087                 m = maskl << (posidx - 5) * 4;
088                 ajtcnt[newcow] += m;
089                 ajtcnt[oldcow] -= m;
090                 break;
091             case 7:
092             case 11:
093             case 15:
094                 m = maskr << (posidx - 5) * 4;
095                 ajtcnt[newcow] += m;
096                 ajtcnt[oldcow] -= m;
097                 break;
098         }
099         cowat[posidx] = newcow;
100         return oldcow;
101     }
102     bool putable(int cowidx, int posidx) const {
103         return !((ajtcnt[cowidx] >> posidx*4) & 0xF);
104     }
105     void dfs(int idx){
106         int oldcow;
107         if(idx == 16){
108             if(!(cnt++)){
109                 for(int i = 0; i < 16; ++i)
110                     putorder[i] = make_pair(dfscow[i], dfspos[i]);
111             }
112             return;
113         }
114         int &cow(dfscow[idx]), &pos(dfspos[idx]);
115         for(cow = 0; cow < 5; ++cow)if(cowleft[cow]){
116             --cowleft[cow];
117             for(pos = 0; pos < 16; ++pos)if(nochange[pos] && putable(cow, pos)){
118                 nochange[pos] = false;
119                 oldcow = replace(cow, pos);
120                 dfs(idx + 1);
121                 replace(oldcow, pos);
122                 nochange[pos] = true;
123             }
124             ++cowleft[cow];
125         }
126     }
127 public:
128     template<class Iter>
129     farm(Iter beg, Iter end): cnt(0), mask (0x011101110111ULL),
130         maskl(0x011001100110ULL), maskr(0x001100110011ULL){
131         fill_n(ajtcnt, 5, 0);
132         fill_n(cowleft, 5, 3);
133         fill_n(nochange, 16, true);
134         for(int i=0; beg != end; ++beg, ++i)
135             addcow(*beg - 'A', i);
136     }
137     void calput(void){
138         int oldcow, &pos(dfspos[0]);
139         dfscow[0] = 3;
140         for(pos = 0; pos < 16; ++pos)if(putable(3, pos)){
141             nochange[pos] = false;
142             oldcow = replace(3, pos);
143             dfs(1);
144             replace(oldcow, pos);
145             nochange[pos] = true;
146         }
147     }
148     ostream& output(ostream& os){
149         for(int i=0; i<16; ++i){
150             div_t pos = div(putorder[i].second, 4);
151             os << char(putorder[i].first + 'A') << ' '
152                 << pos.quot + 1 << ' ' << pos.rem + 1 << '\n';
153         }
154         os << cnt << '\n';
155         return os;
156     }
157 };
158
159 int main(){
160     ifstream fin("wissqu.in");
161     farm wissqu((istream_iterator<char>(fin)), istream_iterator<char>());
162     fin.close();
163     ofstream fout("wissqu.out");
164     wissqu.calput();
165     wissqu.output(fout);
166     fout.close();
167 }