#4110. [Wf2015]Evolution in Parallel

内存限制:128 MiB 时间限制:10 Sec

题目描述

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

输入格式

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

输出格式

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

样例

样例输入


			
2
MC
M
C

样例输出


			
1 1
C
M

数据范围与提示