你在国外度假。这个国家有一个当地的足球联赛，你不知道任何球队的名字。然而，你找到了本赛季所有比赛的结果表，每场比赛旁边都写着两支参赛球队名字的拼接。

总共有 $n$ 支球队，命名为 $s_1, s_2, \dots, s_n$。对于每一对有序的 $i \neq j$，你都已知 $s_i + s_j$ 的拼接结果。请找出球队名称 $s_1, s_2, \dots, s_n$。球队名称必须是非空的，但它们不需要互不相同。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 500$)。

接下来的 $n$ 行，每行包含 $n$ 个字符串，即拼接后的球队名称表。第 $i$ 行的第 $j$ 个字符串，当 $i \neq j$ 时为 $s_i + s_j$，当 $i = j$ 时为 “*”。拼接后的球队名称由小写字母 a-z 组成。

拼接后的球队名称总字符数最多为 $10^6$。

输出格式

如果没有解，输出 “NONE”。

如果有多个解，输出 “MANY”。

如果存在唯一解，输出 “UNIQUE”，随后输出 $n$ 行，包含 $s_1, s_2, \dots, s_n$。

样例

样例输入 1

3
* difaik difhammarby
aikdif * aikhammarby
hammarbydif hammarbyaik *

样例输出 1

UNIQUE
dif
aik
hammarby

样例输入 2

2
* aaaa
aaaa *

样例输出 2

MANY

样例输入 3

3
* a ab
a * b
ba b *

样例输出 3

NONE

样例输入 4

2
* zz
zz *

样例输出 4

UNIQUE
z
z