Description

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

Format

Input

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

Output

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

Samples

2
MC
M
C

1 1
C
M