Background

Translated from ROI 2021 D1T1.

Problem Description

A punched card is a strip consisting of $m$ small squares, where each square either contains a lowercase English letter or is a hole.

There are $n$ such punched cards. Given a string $s$ of length $m$, arrange all punched cards in some order so that after stacking them from top to bottom, the result becomes $s$. In other words, you need to determine the order of the punched cards. When they are stacked together, for every position $i(1 \le i \le m)$, the $i$-th character of the string $s$ must be the same as the character on the first punched card (from top to bottom) that has a letter at position $i$.

If for some $i$, there is no punched card that has a letter at this position, then it is impossible to obtain the target string $s$.

Input Format

The first line contains two integers $n,m(1 \le n,m \le 10^5)$, representing the number of punched cards and the number of squares.

The second line contains a string $s$ of length $m$, consisting of lowercase English letters.

In the next $n$ lines, each line describes one punched card.

First, an integer $k_i(0\le k_i\le m)$ is given, meaning how many positions on this punched card contain letters. It is guaranteed that the sum of all $k_i$ does not exceed $2\times 10^5$.

Then follows the description of the letters on this punched card: for each integer $j(1 \le j \le k_i)$, there is an integer $a_{i,j}$ and a character $c_{i,j}$ ($1 \le a_{i,j} \le m$, $c_{i,j}$ is a lowercase English letter), meaning that the character at position $a_{i,j}$ is $c_{i,j}$. All other positions are holes. It is guaranteed that the positions with letters on each punched card are in increasing order, i.e., $\forall1 \le j < k_,a_{i,j} < a_{i,{j+1}}$.

Output Format

If there exists a correct way to arrange the punched cards, output $n$ integers $p_1,p_2,\dots,p_n(1 \le pi \le n)$, where $p_1$ is the index of the top card, $p_2$ is the index of the second card, and so on, and $p_n$ is the index of the bottom card.

If there are multiple possible answers, you may output any of them. If there is no correct arrangement, output -1.

1 1
a
1 1 a

1

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

3 1 2

2 2
aa
2 1 a 2 b
2 1 b 2 a

-1

Hint

Explanation for sample $2$:

Constraints:

Translated by ChatGPT 5