Polycarp has just launched his new startup idea.这个利基市场相当自由,而且关键的发展方向听起来确实很有前途,所以他很容易就找到了一些准备赞助该公司的投资者。 However, he is yet to name the startup!
Actually, 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.
此外,每个投资者都在名称中选择了一些索引,并选择了一组可以去那里的字母。不同投资者选择的指数是两两不同的。如果某些指数没有被任何投资者选择,那么任何字母都可以到那里。
最后,Polycarp 确信字典顺序上最小的名称是最好的。 (比如你认为 Google 为何决定成为 Alphabet?)
更正式地说,您将获得一个由从“a”到“f”的小写拉丁字母组成的字符串。您可以任意次数地交换任何位置的字母(零交换也是可能的)。
您可以获得的最小的字典顺序名称是多少,以使每个位置的字母都在允许的字母之内?
如果 Polycarp 无法产生任何有效名称,则打印“Impossible”。
输入
第一行是字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — Polycarp 提出的名字。该字符串仅包含从“a”到“f”的小写拉丁字母。
第二行包含一个整数 $$$m$$$ ($$$0 \le m \le |s|$$$) — 投资者数量。
接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含整数 $$$pos_i$$$ 和 $$$pos_i$$$ 允许的非空字符串 ($$$1 \le pos_i \le |s|$$$)。每个字符串包含从“a”到“f”的成对不同字母。 $$$pos_1, pos_2, \dots, pos_m$$$ 成对不同。如果字符串的任何位置没有出现在投资者的要求中,则任何字母都可以出现在该位置。
输出
如果 Polycarp 无法产生任何有效名称,则打印“Impossible”。
否则,打印 Polycarp 通过交换字符串 $$$s$$$ 中的字母可以获得的最小字典顺序名称,使得每个位置的字母都在允许的范围内。
示例
输入 #1
bedefead 5 2 e 1 dc 5 b 7 ef 6 ef
输出 #1
deadbeef
输入 #2
abacaba 0
输出 #2
aaaabbc
输入 #3
fc 2 1 cfab 2 f
输出 #3
cf