[Wf2015]Evolution in Parallel

时间限制:10s      空间限制:128MB

题目描述

给n个只包含A、C、M的字符串,你需要将其分成两列,使每列中的相邻字符串前一个是后一个的子序列,且每列的最后一个字符串都是一个给定字符串s的子序列。


输入格式

第一行一个数n,第二行为一个字符串s,第三行到最后一行为n个字符串。


输出格式

 若无解输出impossible,否则第一行输出两个数,表示两列的长度,之后n行先描述第一列,再描述第二列。


样例输入

2
MC
M
C

样例输出

1 1
C
M

提示

没有写明提示


题目来源

鸣谢talw001提供译文及SPJ