{"raw_statement":[{"iden":"statement","content":"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.\n\nEach 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.\n\nAndres 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.\n\nFirst line of input consists of the ultimate magic spell $s$, which is a string consisting of at most $2 * 10^5$ english lowercase characters.\n\nSecond line of input consists of a single integer $n$ — The number of spells in the UNAL.\n\nNext $n$ ($1 <= n <= 10^5$) lines follow, the $i -t h$ line consists of a non-empty string $a_i$ — The $i -t h$ spell of the UNAL with some (possibly zero) characters added at the end.\n\nIt is guaranteed that the total number of characters in the UNAL with modifications is at most $2 * 10^5$\n\nOutput 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.\n\n"},{"iden":"input","content":"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 <= n <= 10^5$) lines follow, the $i -t h$ line consists of a non-empty string $a_i$ — The $i -t h$ 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$"},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\Sigma^* $ be the ultimate magic spell, where $ \\Sigma $ is the set of lowercase English letters.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of modified spells.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ a_i \\in \\Sigma^* $ be the $ i $-th modified spell.\n\n**Constraints**  \n1. $ |s| \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq n \\leq 10^5 $  \n3. $ \\sum_{i=1}^n |a_i| \\leq 2 \\cdot 10^5 $  \n4. Each $ a_i $ is non-empty.  \n5. Every valid spell is a non-empty subsequence of $ s $.\n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $, find the longest prefix $ p_i $ of $ a_i $ such that $ p_i $ is a subsequence of $ s $.  \nIf no such non-empty prefix exists, output \"IMPOSSIBLE\".  \nOtherwise, output $ p_i $.","simple_statement":"Given a string `s` and a list of `n` modified strings, for each modified string, find the longest prefix that is a subsequence of `s`. If no such prefix exists, output \"IMPOSSIBLE\".","has_page_source":false}