{"raw_statement":[{"iden":"statement","content":"Polycarp has just launched his new startup idea. The niche is pretty free and the key vector of development sounds really promising, so he easily found himself some investors ready to sponsor the company. However, he is yet to name the startup!\n\nActually, Polycarp has already came up with the name but some improvement to it will never hurt. So now he wants to swap letters at some positions in it to obtain the better name. It isn't necessary for letters to be adjacent.\n\nIn addition, each of the investors has chosen some index in the name and selected a set of letters that can go there. Indices chosen by different investors are pairwise distinct. If some indices aren't chosen by any investor then any letter can go there.\n\nFinally, Polycarp is sure that the smallest lexicographically name is the best. (Like why do you think Google decided to become Alphabet?)\n\nMore formally, you are given a string consisting of lowercase Latin letters from \"_a_\" to \"_f_\". You can swap letters at any positions arbitrary number of times (zero swaps is also possible).\n\nWhat is the smallest lexicographically name you can obtain such that the letter at every position is among the allowed letters?\n\nIf Polycarp can't produce any valid name then print \"_Impossible_\"."},{"iden":"input","content":"The first line is the string $s$ ($1 \\le |s| \\le 10^5$) — the name Polycarp has came up with. The string consists only of lowercase Latin letters from \"_a_\" to \"_f_\".\n\nThe second line contains a single integer $m$ ($0 \\le m \\le |s|$) — the number of investors.\n\nThe $i$\\-th of the next $m$ lines contain an integer number $pos_i$ and a non-empty string of allowed characters for $pos_i$ ($1 \\le pos_i \\le |s|$). Each string contains pairwise distinct letters from \"_a_\" to \"_f_\". $pos_1, pos_2, \\dots, pos_m$ are pairwise distinct. If any position of the string doesn't appear in the investors demands then any letter can go in this position."},{"iden":"output","content":"If Polycarp can't produce any valid name then print \"_Impossible_\".\n\nOtherwise print the smallest lexicographically name Polycarp can obtain by swapping letters in string $s$ such that the letter at every position is among the allowed ones."},{"iden":"examples","content":"Input\n\nbedefead\n5\n2 e\n1 dc\n5 b\n7 ef\n6 ef\n\nOutput\n\ndeadbeef\n\nInput\n\nabacaba\n0\n\nOutput\n\naaaabbc\n\nInput\n\nfc\n2\n1 cfab\n2 f\n\nOutput\n\ncf"}],"translated_statement":[{"iden":"statement","content":"Polycarp 刚刚推出了他的新创业点子。这个细分市场非常自由，关键的发展方向听起来极具前景，因此他轻松找到了一些准备赞助公司的投资者。然而，他尚未为公司命名！\n\n实际上，Polycarp 已经想好了名字，但进一步的改进永远不会有害。因此，他希望交换名字中某些位置的字母，以获得更好的名称。字母不需要相邻。\n\n此外，每位投资者都选择了一个名字中的索引，并为该位置选定了一组允许的字母。不同投资者选择的索引互不相同。如果某个位置未被任何投资者选择，则该位置可以放置任意字母。\n\n最后，Polycarp 确信字典序最小的名字是最好的。（就像你认为 Google 为何决定更名为 Alphabet？）\n\n更正式地，你被给定一个由小写拉丁字母 \"_a_\" 到 \"_f_\" 组成的字符串。你可以任意次交换任意位置的字母（允许零次交换）。\n\n请问你能获得的字典序最小的名字是什么，使得每个位置上的字母都在允许的字母集合中？\n\n如果 Polycarp 无法生成任何有效名称，则输出 \"_Impossible_\"。\n\n第一行是字符串 $s$ ($1 lt.eq | s | lt.eq 10^5$) —— Polycarp 想出的名字。该字符串仅包含小写拉丁字母 \"_a_\" 到 \"_f_\"。\n\n第二行包含一个整数 $m$ ($0 lt.eq m lt.eq | s |$) —— 投资者的数量。\n\n接下来的 $m$ 行中，第 $i$ 行包含一个整数 $p o s_i$ 和一个非空字符串，表示位置 $p o s_i$ 允许的字符集合 ($1 lt.eq p o s_i lt.eq | s |$)。每个字符串包含互不相同的字母，范围为 \"_a_\" 到 \"_f_\"。$p o s_1, p o s_2, dots.h, p o s_m$ 互不相同。如果字符串的某个位置未出现在投资者的要求中，则该位置可以放置任意字母。\n\n如果 Polycarp 无法生成任何有效名称，则输出 \"_Impossible_\"。\n\n否则，输出 Polycarp 通过交换字符串 $s$ 中的字母所能获得的字典序最小的名字，使得每个位置上的字母都在允许的集合中。"},{"iden":"input","content":"第一行是字符串 $s$ ($1 lt.eq | s | lt.eq 10^5$) —— Polycarp 想出的名字。该字符串仅包含小写拉丁字母 \"_a_\" 到 \"_f_\"。第二行包含一个整数 $m$ ($0 lt.eq m lt.eq | s |$) —— 投资者的数量。第 $i$ 行包含一个整数 $p o s_i$ 和一个非空字符串，表示位置 $p o s_i$ 允许的字符集合 ($1 lt.eq p o s_i lt.eq | s |$)。每个字符串包含互不相同的字母，范围为 \"_a_\" 到 \"_f_\"。$p o s_1, p o s_2, dots.h, p o s_m$ 互不相同。如果字符串的某个位置未出现在投资者的要求中，则该位置可以放置任意字母。"},{"iden":"output","content":"如果 Polycarp 无法生成任何有效名称，则输出 \"_Impossible_\"。否则，输出 Polycarp 通过交换字符串 $s$ 中的字母所能获得的字典序最小的名字，使得每个位置上的字母都在允许的集合中。"},{"iden":"examples","content":"输入\nbedefead\n5\n2 e\n1 d\nc\n5 b\n7 ef\n6 ef\n输出\ndeadbeef\n\n输入\nabacaba\n0\n输出\naaaabbc\n\n输入\nfc\n2\n1 cf\nab\n2 f\n输出\ncf"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\{a,b,c,d,e,f\\}^n $ be the initial string of length $ n = |s| $.  \nLet $ m \\in \\mathbb{Z}_{\\geq 0} $ be the number of investors.  \nLet $ P \\subseteq \\{1, \\dots, n\\} $ be the set of positions constrained by investors.  \nFor each $ i \\in P $, let $ A_i \\subseteq \\{a,b,c,d,e,f\\} $ be the set of allowed characters at position $ i $.  \nFor each $ j \\notin P $, define $ A_j = \\{a,b,c,d,e,f\\} $ (unconstrained).  \n\nLet $ c : \\{a,b,c,d,e,f\\} \\to \\mathbb{Z}_{\\geq 0} $ be the frequency count of each character in $ s $, i.e., $ c(\\ell) = |\\{ k \\in \\{1,\\dots,n\\} \\mid s_k = \\ell \\}| $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq m \\leq n $  \n3. For each $ i \\in P $, $ A_i \\neq \\emptyset $ and $ A_i \\subseteq \\{a,b,c,d,e,f\\} $  \n4. All $ pos_i $ are distinct and $ 1 \\leq pos_i \\leq n $  \n5. The multiset of characters in the output string must equal the multiset of characters in $ s $ (i.e., frequencies preserved under swapping)  \n6. For each position $ i \\in \\{1,\\dots,n\\} $, the character assigned to position $ i $ must belong to $ A_i $\n\n**Objective**  \nFind the lexicographically smallest string $ t \\in \\{a,b,c,d,e,f\\}^n $ such that:  \n- $ t_i \\in A_i $ for all $ i \\in \\{1,\\dots,n\\} $,  \n- $ c(\\ell) = |\\{ i \\in \\{1,\\dots,n\\} \\mid t_i = \\ell \\}| $ for all $ \\ell \\in \\{a,b,c,d,e,f\\} $,  \n\nIf no such $ t $ exists, output \"Impossible\".","simple_statement":null,"has_page_source":false}