CF1009G Allowed Letters

Polycarp 刚刚启动了他的新创业项目。这个领域相当空白，发展的关键方向也非常有前景，所以他很容易就找到了愿意投资公司的投资人。然而，他还没有给公司起名字！ 实际上，Polycarp 已经想好了名字，但对它进行一些改进总是好的。所以现在他想通过交换名字中某些位置的字母来获得一个更好的名字。字母不一定要相邻才可以交换。 此外，每位投资人都选择了名字中的某个位置，并指定了一组可以放在该位置的字母。不同投资人选择的位置互不相同。如果某些位置没有被任何投资人选择，那么这些位置可以放任意字母。 最后，Polycarp 确信字典序最小的名字就是最好的名字。（比如你觉得 Google 为什么要改名叫 Alphabet？） 更正式地说，给定一个只包含小写拉丁字母 $a$ 到 $f$ 的字符串。你可以任意次数交换任意位置的字母（也可以不交换）。 每位投资人都指定了某个位置和该位置允许的字母集合。不同投资人指定的位置互不相同。如果某些位置没有被指定，则这些位置可以放任意字母。 请你求出通过交换字母后，满足每个位置的限制条件下，字典序最小的名字。如果无法得到合法的名字，输出 "Impossible"。

第一行是字符串 $s$（$1 \le |s| \le 10^5$）——Polycarp 想到的名字。字符串只包含小写拉丁字母 $a$ 到 $f$。 第二行包含一个整数 $m$（$0 \le m \le |s|$）——投资人的数量。 接下来的 $m$ 行，每行包含一个整数 $pos_i$ 和一个非空字符串，表示 $pos_i$ 位置允许的字母集合（$1 \le pos_i \le |s|$）。每个字符串只包含 $a$ 到 $f$ 中互不相同的字母。$pos_1, pos_2, \dots, pos_m$ 互不相同。如果某个位置没有被指定，则该位置可以放任意字母。

如果无法得到合法的名字，输出 "Impossible"。 否则，输出通过交换字母后，满足所有限制条件下字典序最小的名字。

由 ChatGPT 4.1 翻译