#P18216. The Devil

The Devil

The Devil

缩写可以让表达变得简洁,但不同事物使用相同缩写会产生混淆。例如,China Collegiate Programming Contest、China Car Performance Challenge 和 Competition and Consumer Protection Commission 都可以缩写为 CCPC。

现在有 nn 个短语,每个短语由若干个只含英文字母的单词组成。一个短语的缩写按如下方式构造:

  • 对短语中的每个单词,分别选择它的一个非空前缀;
  • 按原单词顺序,将选出的所有前缀直接拼接起来,得到一个不含空格的字符串。

例如,ChCoPrCo 和 CCPContest 都是 China Collegiate Programming Contest 的合法缩写,CCCP 和 CCPiC 则不是。

每个短语的选择彼此独立。即使某个单词出现在多个短语中,也不要求它在不同短语里选择相同的前缀。大小写字母视为不同字符。

请为这 nn 个短语各选择一个缩写,使所有缩写字符串两两不同,并使它们的长度总和最小。

输入格式

第一行包含一个整数 nn,表示短语数。

接下来 nn 行,每行包含一个非空短语。短语中的相邻单词用一个空格分隔。

输出格式

如果不存在满足要求的方案,输出一行 no solution。

否则输出 nn 行,第 ii 行包含第 ii 个输入短语所选的缩写。所有缩写必须合法、两两不同,且总长度达到最小值。若有多个最优方案,输出任意一个。

数据范围

  • 1≤n≤1281\le n\le128;
  • 每个短语包含 11 到 128128 个单词;
  • 每个单词包含 11 到 128128 个大写或小写英文字母;
  • 保证输入的短语两两不同。

样例 1

5
automated teller machine
active teller machine
active trouble maker
always telling misinformation
American Teller Machinery
atm
atma
actm
atem
ATM

样例 2

5
Forest Conservation Committee Forum
Fuming Corruption Collusion Federation
Fulsome Cash Concealment Foundation
Funky Crony Capitalism Facilitator
Funny Cocky Cocky Funny
FCCF
FCoCF
FuCCF
FCCFa
FCCFu

样例 3

3
A AA
AA A
A A A
no solution