#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0);
#define forn(i, n) for (int i = 0; i < n; i++)
#define fornm(i, n, m) for (int i = n; i <= m; i++)
#define rforn(in, n) for (int i = n - 1; i >= 0; i--)
#define all(x) x.begin(), x.end()
#define len(x) int(x.size())
#define ms(x, n) memset(x, n, sizeof(x))
#define find(x, n) find(all(x), n) != x.end()
#define suma(a, b) ((a % MOD) + (b $ MOD)) % MOD
#define resta(a, b) ((a % MOD) - (b $ MOD)) % MOD
//" \n"[i == n - 1]
using namespace std;
class HashedString {
private:
// change M and B if you want
static const long long M = 1e9 + 9;
static const long long B = 9973;
// pow[i] contains B^i % M
static vector<long long> pow;
// p_hash[i] is the hash of the first i characters of the given string
vector<long long> p_hash;
public:
HashedString(const string &s) : p_hash(s.size() + 1) {
while (pow.size() < s.size()) { pow.push_back((pow.back() * B) % M); }
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
}
}
long long get_hash(int start, int end) {
long long raw_val =
(p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
return (raw_val % M + M) % M;
}
};
vector<long long> HashedString::pow = {1};
void solve()
{
int n; cin >> n;
string grid[n][n];
forn(i, n) {
forn (j, n) {
cin >> grid[i][j];
}
}
if (n == 2) {
HashedString one(grid[0][1]);
HashedString two(grid[1][0]);
int oc = 0;
int idx = -1;
set< array<string, 2> > ans;
forn (i, len(grid[0][1])-1) {
if (
one.get_hash(0, i) == two.get_hash(len(grid[1][0])-i-1, len(grid[1][0])-1) &&
one.get_hash(i+1, len(grid[0][1])-1) == two.get_hash(0, len(grid[1][0])-i-2)) {
oc++;
idx = i;
}
}
if (oc == 0) {
cout << "NONE\n";
} else if (oc > 1) {
cout << "MANY\n";
} else {
cout << "UNIQUE\n";
cout << grid[0][1].substr(0, idx+1) << endl;
cout << grid[1][0].substr(0, len(grid[0][1])-idx-1) << endl;
}
} else {
ll sum = 0;
vector<ll> sumRow(n, 0LL);
forn(i, n) {
forn (j, n) {
if (i == j) continue;
sum += len(grid[i][j]);
sumRow[i] += len(grid[i][j]);
}
}
sum /= ((2*n)-2);
vector<string> ans;
bool ok = true;
forn(i, n) {
ll strLen = (sumRow[i]-sum)/(n-2);
string o = "";
if (strLen <= 0) {
ok = false;
break;
}
forn(j, strLen) {
o += grid[i][(i+1)%n][j];
}
ans.push_back(o);
}
if (len(ans) != n) {
cout << "NONE\n";
return;
}
forn(i, n) {
forn(j, n) {
if (i == j) continue;
if (ans[i]+ans[j] != grid[i][j]) {
ok = false;
break;
}
}
}
if (!ok) {
cout << "NONE\n";
return;
}
cout << "UNIQUE\n";
for (auto y: ans) cout << y << endl;
}
}
int main()
{
fast;
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwojZGVmaW5lIGVuZGwgJ1xuJwojZGVmaW5lIGZhc3QgICAgICAgICAgICAgICAgICAgIFwKICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyBcCiAgY2luLnRpZSgwKTsKCiNkZWZpbmUgZm9ybihpLCBuKSBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKI2RlZmluZSBmb3JubShpLCBuLCBtKSBmb3IgKGludCBpID0gbjsgaSA8PSBtOyBpKyspCiNkZWZpbmUgcmZvcm4oaW4sIG4pIGZvciAoaW50IGkgPSBuIC0gMTsgaSA+PSAwOyBpLS0pCgojZGVmaW5lIGFsbCh4KSB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSBsZW4oeCkgaW50KHguc2l6ZSgpKQoKI2RlZmluZSBtcyh4LCBuKSBtZW1zZXQoeCwgbiwgc2l6ZW9mKHgpKQoKI2RlZmluZSBmaW5kKHgsIG4pIGZpbmQoYWxsKHgpLCBuKSAhPSB4LmVuZCgpCgojZGVmaW5lIHN1bWEoYSwgYikgKChhICUgTU9EKSArIChiICQgTU9EKSkgJSBNT0QKI2RlZmluZSByZXN0YShhLCBiKSAoKGEgJSBNT0QpIC0gKGIgJCBNT0QpKSAlIE1PRAoKLy8iIFxuIltpID09IG4gLSAxXQp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgSGFzaGVkU3RyaW5nIHsKICBwcml2YXRlOgoJLy8gY2hhbmdlIE0gYW5kIEIgaWYgeW91IHdhbnQKCXN0YXRpYyBjb25zdCBsb25nIGxvbmcgTSA9IDFlOSArIDk7CglzdGF0aWMgY29uc3QgbG9uZyBsb25nIEIgPSA5OTczOwoKCS8vIHBvd1tpXSBjb250YWlucyBCXmkgJSBNCglzdGF0aWMgdmVjdG9yPGxvbmcgbG9uZz4gcG93OwoKCS8vIHBfaGFzaFtpXSBpcyB0aGUgaGFzaCBvZiB0aGUgZmlyc3QgaSBjaGFyYWN0ZXJzIG9mIHRoZSBnaXZlbiBzdHJpbmcKCXZlY3Rvcjxsb25nIGxvbmc+IHBfaGFzaDsKCiAgcHVibGljOgoJSGFzaGVkU3RyaW5nKGNvbnN0IHN0cmluZyAmcykgOiBwX2hhc2gocy5zaXplKCkgKyAxKSB7CgkJd2hpbGUgKHBvdy5zaXplKCkgPCBzLnNpemUoKSkgeyBwb3cucHVzaF9iYWNrKChwb3cuYmFjaygpICogQikgJSBNKTsgfQoKCQlwX2hhc2hbMF0gPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgcy5zaXplKCk7IGkrKykgewoJCQlwX2hhc2hbaSArIDFdID0gKChwX2hhc2hbaV0gKiBCKSAlIE0gKyBzW2ldKSAlIE07CgkJfQoJfQoKCWxvbmcgbG9uZyBnZXRfaGFzaChpbnQgc3RhcnQsIGludCBlbmQpIHsKCQlsb25nIGxvbmcgcmF3X3ZhbCA9CgkJICAgIChwX2hhc2hbZW5kICsgMV0gLSAocF9oYXNoW3N0YXJ0XSAqIHBvd1tlbmQgLSBzdGFydCArIDFdKSk7CgkJcmV0dXJuIChyYXdfdmFsICUgTSArIE0pICUgTTsKCX0KfTsKdmVjdG9yPGxvbmcgbG9uZz4gSGFzaGVkU3RyaW5nOjpwb3cgPSB7MX07Cgp2b2lkIHNvbHZlKCkKewogIGludCBuOyBjaW4gPj4gbjsKICBzdHJpbmcgZ3JpZFtuXVtuXTsKICBmb3JuKGksIG4pIHsKICAgIGZvcm4gKGosIG4pIHsKICAgICAgY2luID4+IGdyaWRbaV1bal07CiAgICB9CiAgfQoKICBpZiAobiA9PSAyKSB7CiAgICBIYXNoZWRTdHJpbmcgb25lKGdyaWRbMF1bMV0pOwogICAgSGFzaGVkU3RyaW5nIHR3byhncmlkWzFdWzBdKTsKICAgIGludCBvYyA9IDA7CiAgICBpbnQgaWR4ID0gLTE7CiAgICBzZXQ8IGFycmF5PHN0cmluZywgMj4gPiBhbnM7CiAgICBmb3JuIChpLCBsZW4oZ3JpZFswXVsxXSktMSkgewogICAgICBpZiAoCiAgICAgICAgb25lLmdldF9oYXNoKDAsIGkpID09IHR3by5nZXRfaGFzaChsZW4oZ3JpZFsxXVswXSktaS0xLCBsZW4oZ3JpZFsxXVswXSktMSkgJiYKICAgICAgICBvbmUuZ2V0X2hhc2goaSsxLCBsZW4oZ3JpZFswXVsxXSktMSkgPT0gdHdvLmdldF9oYXNoKDAsIGxlbihncmlkWzFdWzBdKS1pLTIpKSB7CiAgICAgICAgb2MrKzsKICAgICAgICBpZHggPSBpOwogICAgICB9CiAgICB9CiAgICBpZiAob2MgPT0gMCkgewogICAgICBjb3V0IDw8ICJOT05FXG4iOwogICAgfSBlbHNlIGlmIChvYyA+IDEpIHsKICAgICAgY291dCA8PCAiTUFOWVxuIjsKICAgIH0gZWxzZSB7CiAgICAgIGNvdXQgPDwgIlVOSVFVRVxuIjsKICAgICAgY291dCA8PCBncmlkWzBdWzFdLnN1YnN0cigwLCBpZHgrMSkgPDwgZW5kbDsKICAgICAgY291dCA8PCBncmlkWzFdWzBdLnN1YnN0cigwLCBsZW4oZ3JpZFswXVsxXSktaWR4LTEpIDw8IGVuZGw7CiAgICB9CiAgfSBlbHNlIHsKICAgIGxsIHN1bSA9IDA7CiAgICB2ZWN0b3I8bGw+IHN1bVJvdyhuLCAwTEwpOwogICAgZm9ybihpLCBuKSB7CiAgICAgIGZvcm4gKGosIG4pIHsKICAgICAgICBpZiAoaSA9PSBqKSBjb250aW51ZTsKICAgICAgICBzdW0gKz0gbGVuKGdyaWRbaV1bal0pOwogICAgICAgIHN1bVJvd1tpXSArPSBsZW4oZ3JpZFtpXVtqXSk7CiAgICAgIH0KICAgIH0KCiAgICBzdW0gLz0gKCgyKm4pLTIpOwogICAgdmVjdG9yPHN0cmluZz4gYW5zOwogICAgYm9vbCBvayA9IHRydWU7CiAgICBmb3JuKGksIG4pIHsKICAgICAgbGwgc3RyTGVuID0gKHN1bVJvd1tpXS1zdW0pLyhuLTIpOwogICAgICBzdHJpbmcgbyA9ICIiOwogICAgICBpZiAoc3RyTGVuIDw9IDApIHsKICAgICAgICBvayA9IGZhbHNlOwogICAgICAgIGJyZWFrOwogICAgICB9CiAgICAgIGZvcm4oaiwgc3RyTGVuKSB7CiAgICAgICAgbyArPSBncmlkW2ldWyhpKzEpJW5dW2pdOwogICAgICB9CiAgICAgIGFucy5wdXNoX2JhY2sobyk7CiAgICB9CgogICAgaWYgKGxlbihhbnMpICE9IG4pIHsKICAgICAgY291dCA8PCAiTk9ORVxuIjsKICAgICAgcmV0dXJuOwogICAgfQoKICAgIGZvcm4oaSwgbikgewogICAgICBmb3JuKGosIG4pIHsKICAgICAgICBpZiAoaSA9PSBqKSBjb250aW51ZTsKICAgICAgICBpZiAoYW5zW2ldK2Fuc1tqXSAhPSBncmlkW2ldW2pdKSB7CiAgICAgICAgICBvayA9IGZhbHNlOwogICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICB9CiAgICB9CgogICAgaWYgKCFvaykgewogICAgICBjb3V0IDw8ICJOT05FXG4iOwogICAgICByZXR1cm47CiAgICB9CiAgICBjb3V0IDw8ICJVTklRVUVcbiI7CiAgICBmb3IgKGF1dG8geTogYW5zKSBjb3V0IDw8IHkgPDwgZW5kbDsKICB9Cn0KCmludCBtYWluKCkKewogIGZhc3Q7CgogIGludCB0ID0gMTsKICAvL2NpbiA+PiB0OwoKICB3aGlsZSAodC0tKQogIHsKICAgIHNvbHZlKCk7CiAgfQoKICByZXR1cm4gMDsKfQ==