407243: GYM102700 M Magic spells

The Ultra Nice Abracadabra List (UNAL) is a list of $$$n$$$ magic spells for young student wizards in the school of magic, a magic spell is a sequence of English characters which can be used to make something magic, all magic spells have the incredible property of being subsequences of the ultimate magic spell $$$s$$$. Actually, all non-empty subsequences of $$$s$$$ are spells, although not all are written in the UNAL.

Each student has its own copy of the UNAL when entering into the school, in particular, Andres, who is a new student, just got his copy of the UNAL. However, many of his mean (potential dark wizards) classmates took his copy of the UNAL and wrote some (possibly zero) characters after each of the spells in the list.

Andres is not dumb and he realized what his classmates did. He knows $$$s$$$ and for him, it is enough for each line in the modified UNAL to get the longest prefix that is also a spell. Help Andres with this non-magic work.

First line of input consists of the ultimate magic spell $$$s$$$, which is a string consisting of at most $$$2 *10^5$$$ english lowercase characters.

Second line of input consists of a single integer $$$n$$$ — The number of spells in the UNAL.

Next $$$n$$$ ($$$1 \leq n \leq 10^5$$$) lines follow, the $$$i-th$$$ line consists of a non-empty string $$$a_i$$$ — The $$$i-th$$$ spell of the UNAL with some (possibly zero) characters added at the end.

It is guaranteed that the total number of characters in the UNAL with modifications is at most $$$2*10^5$$$

Output consists of $$$n$$$ lines, each line should consists of the longest possible spell, if it is not possible to make a spell print "IMPOSSIBLE" (without quotes) instead.

abracadabra
5
abra
cadabra
abcd
dcba
magic

abra
cadabra
abcd
d
IMPOSSIBLE