Deciphering Ice-Peak City

Professor Shi discovered an ancient city, Ice‐Peak City, on the Yunmeng Plateau. In the ruins he found 12 giant stele inscribed in a mysterious script, which he calls Ice‐Peak Script. The script consists only of declarative sentences, and its vocabulary contains exactly three types of words: noun (n), verb (v), and auxiliary (a). Its grammar is very simple, and the only sentence forms allowed are:

$$S \to n\;v\quad\;\text{or}\quad S \to n\;a\;v\quad\;\text{or}\quad S \to n\;v\;n\quad\;\text{or}\quad S \to n\;a\;v\;n $$

Moreover, in Ice‐Peak Script there are no spaces between sentences or words. Your task is to segment a given article (a continuous string of lowercase letters) into a sequence of valid sentences according to the above grammar. Among all possible segmentations, you must choose one that uses the minimum number of sentences; and under that condition, one that uses the minimum total number of words.

You are also given a dictionary for Ice‐Peak Script. Each dictionary entry is a word (composed of lowercase letters a–z) along with its type (n, v, or a).

A valid sentence is exactly a sequence of words matching one of the following patterns:

• [n, v]
• [n, a, v]
• [n, v, n]
• [n, a, v, n]

If a segmentation is possible, output the sentences (one per line) with the words separated by a single space. If no valid segmentation exists, output "impossible".

inputFormat

The input consists of multiple lines. The first line contains a nonempty string S representing the Ice‐Peak Script text (a continuous string of lowercase letters). The second line contains an integer m representing the number of words in the dictionary. The following m lines each contain a dictionary entry in the format:

word type

where word is a nonempty string of lowercase letters and type is one of n, v, or a.

outputFormat

If a valid segmentation is found, output the segmented sentences in order. Each sentence should be printed on its own line, with its constituent words separated by a single space. If there is no valid segmentation, output a single line with the word "impossible".

sample

stoneandfoundcity
5
stone n
ice n
and a
found v
city n

stone and found city