Allowed Letters
Contest: Educational Codeforces Round 47 (Rated for Div. 2)
Difficulty rating: 2400
Tags: bitmasks, flows, graph matchings, graphs, greedy

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!

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.

In 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.

Finally, Polycarp is sure that the smallest lexicographically name is the best. (Like why do you think Google decided to become Alphabet?)

More 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).

What is the smallest lexicographically name you can obtain such that the letter at every position is among the allowed letters?

If Polycarp can't produce any valid name then print "Impossible".

Input format:
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".

The second line contains a single integer $$$m$$$ ($$$0 \le m \le |s|$$$) — the number of investors.

The $$$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.

Output format:
If Polycarp can't produce any valid name then print "Impossible".

Otherwise 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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
bedefead
5
2 e
1 dc
5 b
7 ef
6 ef

Example output:
deadbeef

Example input:
abacaba
0

Example output:
aaaabbc

Editorial:
The idea of solution is the following: we build the answer letter-by-letter; when choosing a character for some position, we try all possible characters and check that we can build the suffix after placing this character. But we need to somehow do this checking fast.
As in many previous Educational Rounds, in this round some participants' solutions were much easier to write and understand than our own model solution.
Authors' solution (uses network flows):
Let's build a flow network, where we have $$$6$$$ vertices representing the characters of the string and $$$2^6$$$ vertices representing the masks of characters. Add directed edges from the source to every node representing some character with capacity equal to the number of such characters in the original string; also add directed edges from every node representing some character to all vertices representing masks where this character is contained (with infinite capacity); and finally, add a directed edge from every "mask"-node to the sink with capacity equal to the number of positions where this mask of characters is allowed.
If we find maximum flow in this network, we can check that the answer exists, and if it exists, build some answer. Now let's try to build optimal answer by somehow rebuilding the flow in the network.
Suppose we are trying to place a character $$$x$$$ to position containing mask $$$m$$$. To check whether we can do it, we have to try rebuilding the flow in such a way that the edge from vertex corresponding to $$$x$$$ to vertex corresponding to $$$m$$$ has non-zero flow. If it is already non-zero, then we are done; otherwise we may cancel a unit of flow going through an edge from source to $$$x$$$-vertex, then cancel a unit of flow going through an edge from $$$m$$$-vertex to sink, decrease the capacity of these two edges by $$$1$$$ and check that there exists an augmenting path. If it exists, then returning the capacities back and adding one unit of flow through the path $$$source \rightarrow x \rightarrow m \rightarrow sink$$$ actually builds some answer where some character $$$x$$$ is placed on some position with mask $$$m$$$, so we may place it there; otherwise it's impossible.
When we finally decided to place $$$x$$$ on position $$$m$$$, we have to decrease the flow through $$$source \rightarrow x \rightarrow m \rightarrow sink$$$ and the capacities of edges $$$source \rightarrow x$$$ and $$$m \rightarrow sink$$$.
All this algorithm runs in $$$O(n \cdot 2^A \cdot A^2)$$$, where $$$A$$$ is the size of the alphabet.
Participants' solution (uses Hall's theorem):
Hall's theorem allows us to check that we may build the suffix of the answer much easier.
Each time we try to place some character, we need to iterate on all possible subsets of characters we still need to place and check that the number of positions that are suitable for at least one character in a subset is not less than the size of subset (just like in regular Hall's theorem). The key fact here is that if we have, for example, $$$3$$$ characters a yet to place, then we don't need to check any subset containing exactly $$$1$$$ or $$$2$$$ characters a, since the number of "suitable" positions for this subset won't become larger if we add all remaining characters a to a subset. So the subsets we have to consider are limited by the masks of possible characters, and there will be only $$$64$$$ of them.