Evolution in Parallel

Time limit2sMemory limit256 MB

Summary

Decide whether every fossil sequence fits into one of two chains in which each sequence is a subsequence of the next one and of the living species sequence.

Level: Hard8 of 10
Topics: Graph, BFS, String matching
Solved: No attempts yet

Problem

It is 2178, and a research team has found alien life on a distant planet. Only one species lives there, and every organism of that species has the same genetic makeup.

The genetic makeup of an organism is a single sequence of nucleotides. A nucleotide is one of three types, written A (adenine), C (cytosine), and M (muamine). Under one hypothesis, evolution on this planet happens when a new nucleotide is inserted somewhere into the genetic sequence of an existing organism. If the new sequence is an advantage, organisms with it quickly replace the organisms with the old sequence. An evolutionary path is therefore a series of sequences in chronological order in which every sequence is a subsequence of the next one, that is, the earlier sequence is what remains after deleting zero or more letters from the later one.

Researchers first believed that today's species evolved this way from one very simple organism whose sequence held a single nucleotide. Fossil evidence points elsewhere. Your team is testing the parallel evolution hypothesis: two evolutionary paths ran in the manner above, and both ended at the single species living on the planet today.

Every fossil sequence has to be assigned to exactly one of the two paths. The sequences assigned to one path, placed in chronological order, must each be a subsequence of the next one, and the last of them must be a subsequence of the sequence of the species living today. One of the two paths may stay empty.

Decide whether the fossil sequences your team collected are consistent with the parallel evolution hypothesis.

Input

The first line holds an integer $n$ ( $1 \le n \le 4000$ ), the number of nucleotide sequences found in the fossils. The second line holds the nucleotide sequence of the species living on the planet today. Each of the next $n$ lines holds one nucleotide sequence found in the fossils.

Every nucleotide sequence has at least 1 and at most 4000 letters and uses only the upper case letters A, C, and M. All the sequences, including the one of the species living today, are distinct.

Output

Print possible if every fossil sequence can be assigned to one of two evolutionary paths in the way described. Otherwise print impossible.

Examples4

Example 1
Input
```
5
AACCMMAA
ACA
MM
ACMAA
AA
A
```
Expected output
```
possible
```
Example 2
Input
```
3
ACMA
ACM
ACA
AMA
```
Expected output
```
impossible
```
Example 3
Input
```
1
AM
MA
```
Expected output
```
impossible
```
Example 4
Input
```
4
AAAAAA
AA
AAA
A
AAAAA
```
Expected output
```
possible
```