///////////////////////////////////////////////////////////////////////////////
// solution to
http://acm.uva.es/p/v7/715.html
// problem 715
// "Wrong Answer"
///////////////////////////////////////////////////////////////////////////////
// @BEGIN_OF_SOURCE_CODE
// @JUDGE_ID: xxxxxx 715 C++
// if you only use TRACE and printVector for debugging output then defining this
// will remove the output for submitting.
#define NDEBUG
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#ifdef WIN32
#include <sstream>
#else
#include <strstream>
typedef strstream stringstream;
#endif
#ifdef NDEBUG
#define TRACE(x) ((void)0)
#else
#define TRACE(x) cout<< #x ": '"<<( x )<<"'" << endl
#endif
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;
// will create a segment vilolation
void segVilolation() {
vector<double> v;
for(int i = 0; i < 10000; ++i) {
v[i] *= v[i * 5];
}
}
//-----------------------------------------------------------------------------
// Reads a line of input, and adds each value in the line to the vector
// Returns false when it reads EOF
// Returns an empty vector if the line is empty
// Lines with invalid terms are ignored after the first invalid term.
// Vector is cleared before values are added.
//
template<class T>
bool getInputLine(vector<T>& vec)
{
vec.clear();
if (cin.eof()) {
return false;
}
stringstream inLine;
cin.clear();
cin.get(*inLine.rdbuf());
if (cin.fail() && !cin.eof()) {
cin.clear();
}
cin.get(); // get rid of delimiter
while(!inLine.eof())
{
T field;
#ifdef WIN32
inLine >> noskipws >> field;
#else
inLine.unsetf(ios::skipws);
inLine >> field;
#endif
if(!inLine.fail()) {
vec.push_back(field);
}
}
return true;
}
template <class T>
void displayVec(vector< vector <T> > vec) {
#ifndef NDEBUG
for (int i = 0; i < vec.size(); ++i) {
for (int j = 0; j < vec[i].size(); ++j) {
cout << vec[i][j];
}
cout << endl;
}
#endif
}
char gBefore, gAfter; // a rule, set by getRule
vector< vector< char > > gPossibilities; // all the possible alphabets, determined by rules
bool getRule(const string& a, const string& b) {
int len = MIN(a.size(), b.size());
for (int i = 0; i < len; ++i) {
if (a[i] != b[i]) {
gBefore = a[i];
gAfter = b[i];
return true;
}
}
return false;
}
bool isLetterTaken(char c) {
if (gPossibilities.empty()) {
return false;
}
for (int i = 0; i < gPossibilities[0].size(); ++i) {
if (gPossibilities[0][i] == c) {
return true;
}
}
return false;
}
// for all the letters that come after gBefore (including gBefore) in all gPossibilities
// add a new possibility with gAfter after that letter
void addPossibilityBefore(char there, char notThere) {
vector< vector<char> > newPossibilities;
for (int i = 0; i < gPossibilities.size(); ++i) {
bool added = false;
for (int j = 0; j < gPossibilities[i].size(); ++j) {
if (gPossibilities[i][j] == there || added) {
vector<char> possibility;
for (int k = 0; k < gPossibilities[i].size(); ++k) {
possibility.push_back(gPossibilities[i][k]);
if (k == j) {
possibility.push_back(notThere);
}
}
newPossibilities.push_back(possibility);
added = true;
}
}
}
gPossibilities = newPossibilities;
}
void addPossibilityAfter(char there, char notThere) {
vector< vector<char> > newPossibilities;
for (int i = 0; i < gPossibilities.size(); ++i) {
bool seenThere = false;
for (int j = 0; j < gPossibilities[i].size(); ++j) {
if (gPossibilities[i][j] == there || !seenThere) {
vector<char> possibility;
for (int k = 0; k < gPossibilities[i].size(); ++k) {
if (k == j) {
possibility.push_back(notThere);
}
possibility.push_back(gPossibilities[i][k]);
}
newPossibilities.push_back(possibility);
if (gPossibilities[i][j] == there) {
seenThere = true;
}
}
}
}
gPossibilities = newPossibilities;
}
void addPossibilities(vector< vector<char> >& newPossibilities, const vector<char>& possibility, int index) {
for (int i = index; i < possibility.size() + 1; ++i) {
vector<char> newPossibility = possibility;
newPossibility.insert(newPossibility.begin() + index, gBefore);
newPossibility.insert(newPossibility.begin() + i + 1, gAfter);
newPossibilities.push_back(newPossibility);
}
}
void addPossibility() {
vector< vector<char> > newPossibilities;
for (int i = 0; i < gPossibilities.size(); ++i) {
for (int j = 0; j < gPossibilities[i].size() + 1; ++j) {
addPossibilities(newPossibilities, gPossibilities[i], j);
}
}
gPossibilities = newPossibilities;
}
// remove any inconsitent possibilities based on the new rule
void removeInconsistent() {
vector< vector <char> > consistent;
for (int i = 0; i < gPossibilities.size(); ++i) {
bool foundBefore = false;
for (int j = 0; j < gPossibilities[i].size(); ++j) {
if (gPossibilities[i][j] == gBefore) {
foundBefore = true;
} else if (gPossibilities[i][j] == gAfter && foundBefore) {
consistent.push_back(gPossibilities[i]);
break;
}
}
}
gPossibilities = consistent;
}
int main()
{
TRACE("started");
vector<long> input;
getInputLine(input);
assert(input.size() == 1);
int totalCases = input[0];
for (int numCases = 0; numCases < totalCases; ++numCases) {
getInputLine(input);
if (input.empty()) {
break;
}
assert(input.size() == 2);
gPossibilities.clear();
string previousWord;
TRACE(input[1]);
for (int numWords = 0; numWords < input[1]; ++numWords) {
vector<string> word;
getInputLine(word);
if (numWords == 0) {
previousWord = word[0];
continue;
}
if (!getRule(previousWord, word[0])) {
/// TRACE("no rule");
/// TRACE(previousWord);
/// TRACE(word[0]);
previousWord = word[0];
continue;
}
previousWord = word[0];
TRACE(gBefore);
TRACE(gAfter);
if (gPossibilities.empty()) {
vector <char> start;
start.push_back(gBefore);
gPossibilities.push_back(start);
}
// TRACE(1);
// displayVec(gPossibilities);
bool isBeforeTaken = isLetterTaken(gBefore);
bool isAfterTaken = isLetterTaken(gAfter);
if (isBeforeTaken && !isAfterTaken) {
addPossibilityBefore(gBefore, gAfter);
} else if (isAfterTaken && !isBeforeTaken) {
addPossibilityAfter(gAfter, gBefore);
} else if (isAfterTaken && isBeforeTaken) {
removeInconsistent();
} else { // !isAfterTaken && !isBeforeTaken
addPossibility();
}
// TRACE(2);
displayVec(gPossibilities);
}
TRACE(numCases);
//displayVec(gPossibilities);
vector<char> encrypted;
getInputLine(encrypted);
bool isDifferent = false;
for (int i = 1; i < gPossibilities.size(); ++i) {
for (int j = 0; j < gPossibilities[0].size(); ++j) {
if (gPossibilities[0][j] != gPossibilities[i][j]) {
isDifferent = true;
break;
}
}
}
if (gPossibilities[0].size() > input[0]) {
segVilolation();
}
if (!isDifferent && gPossibilities.size() > 0 && gPossibilities[0].size() == input[0] || input[0] < 2) {
for (int i = 0; i < encrypted.size(); ++i) {
bool found = false;
for (int j = 0; j < gPossibilities[0].size(); ++j) {
if (toupper(gPossibilities[0][j]) == toupper(encrypted[i])) {
if (isupper(encrypted[i])) {
cout << ((char) toupper('a' + j));
} else {
cout << ((char) ('a' + j));
}
found = true;
}
}
if (!found) {
cout << encrypted[i];
}
}
cout << endl;
} else {
cout << "Message cannot be decrypted." << endl;
}
}
TRACE("end of run");
return 0;
}
