Punched Cards

Time limit1sMemory limit1024 MB

Summary

Order n punched cards so that, reading each column downward, the first letter encountered spells the target string s, or report that no order works.

Level: Medium7 of 10
Topics: Graph, Topological sort, Greedy, Sorting
Solved: No attempts yet

Problem

$n$ punched cards were found in the warehouse of the company hosting the programming olympiad. A punched card is a strip of $m$ cells, each of which either contains a lowercase English letter or is a hole.

The olympiad jury wants to order all the punched cards so that, when they are placed one under another from top to bottom in this order, the olympiad slogan appears: the given string $s$ of length $m$ .

In other words, fix the order in which the cards are laid and consider an arbitrary position $i$ ( $1 \le i \le m$ ). Then the $i$ -th character of the string $s$ must match the character at position $i$ of the topmost punched card that has a letter at position $i$ . If for some $i$ there is no punched card with a letter at position $i$ , then the required string $s$ is considered impossible to obtain.

Help the jury figure out the order in which the punched cards must be placed.

Fig. 1: The order of the cards from the second sample. The letters visible from above are highlighted

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 100\,000$ ), the number of punched cards and the number of cells, respectively.

The second line contains the string $s$ consisting of $m$ lowercase English letters.

The $i$ -th of the following $n$ lines contains the description of the $i$ -th punched card.

The description begins with an integer $k\_i$ ( $0 \le k\_i \le m$ ), the number of positions with letters on this punched card. The sum of all $k\_i$ is guaranteed not to exceed $200\,000$ .

Then follows the description of the letters on this punched card: $k\_i$ pairs $a\_{i,j}$ , $c\_{i,j}$ ( $1 \le a\_{i,j} \le m$ , $c\_{i,j}$ is a lowercase English letter) for all integers $1 \leq j \leq k\_i$ ; each pair indicates that the character $c\_{i,j}$ is present at position $a\_{i,j}$ . The remaining positions contain holes. The numbers of the positions with letters on a single punched card are guaranteed to be given in increasing order, that is, for any $1 \leq j < k\_i$ we have $a\_{i,j} < a\_{i,j+1}$ .

Output

If there is a way to order the punched cards as required, output $n$ integers $p\_1, p\_2, \ldots, p\_n$ ( $1 \le p\_i \le n$ ), where $p\_1$ is the number of the topmost punched card, $p\_2$ is the number of the second card from the top, and so on up to the card $p\_n$ , which lies at the bottom. If there are several possible answers, you may output any of them.

If there is no way to order the punched cards as required, output the single number $-1$ .

Notes

$n \le 100\,000$
$m \le 100\,000$

Examples3

Example 1
Input
```
1 1
a
1 1 a
```
Expected output
```
1
```

Example 2

Input

3 4
glhf
3 1 r 3 h 4 i
3 1 r 2 l 3 o
2 1 g 4 f

Expected output

3 1 2

Example 3
Input
```
2 2
aa
2 1 a 2 b
2 1 b 2 a
```
Expected output
```
-1
```