21545번 - Перфокарты 서브태스크스페셜 저지다국어

На складе фирмы, на базе которой проходит олимпиада по программированию, были обнаружены $n$ перфокарт. Перфокарта представляет собой полоску из $m$ клеточек, каждая из которых либо содержит строчную английскую букву, либо является отверстием. 

Жюри олимпиады решило упорядочить все перфокарты так, что если расположить их одну под другой сверху вниз в этом порядке, то получится лозунг олимпиады --- заданная строка $s$ длины $m$. 

Иными словами, зафиксируем порядок перфокарт, в котором они будут лежать, и рассмотрим произвольную позицию $i$ ($1 \le i \le m$). Тогда $i$-й символ строки $s$ должен совпадать с символом на $i$-й позиции самой верхней перфокарты, содержащей на позиции $i$ какую-либо букву. Если для какого-то $i$ ни одной перфокарты с буквой в позиции $i$ нет, то считается, что требуемую строку $s$ получить невозможно.

Помогите жюри понять, в каком порядке необходимо расположить перфокарты.

Рис. 1: Порядок карт из второго примера. Выделены те буквы, которые видны сверху

Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 100\,000$), обозначающих число перфокарт и количество клеток соответственно.

Вторая строка содержит строку $s$, состоящую из $m$ строчных английских букв.

В $i$-й из следующих $n$ строк находится описание $i$-й перфокарты.

Описание начинается с целого числа $k_i$ ($0 \le k_i \le m$), обозначающего количество позиций с буквами в этой перфокарте. Гарантируется, что сумма всех значений $k_i$ не превышает $200\,000$.

Далее следует описание букв на этой перфокарте: $k_i$ пар $a_{i,j}$, $c_{i,j}$ ($1 \le a_{i,j} \le m$, $c_{i,j}$ является строчной английской буквой) для всех целых $1 \leq j \leq k_i$; каждая пара обозначает наличие символа $c_{i,j}$ на позиции $a_{i,j}$. Остальные позиции содержат отверстия. Гарантируется, что номера позиций с буквами для одной перфокарты приведены по возрастанию, то есть для любого $1 \leq j < k_i$ верно $a_{i,j} < a_{i,j+1}$.

Если способ упорядочить перфокарты требуемым способом существует, выведите $n$ целых чисел $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), где $p_1$ --- номер самой верхней перфокарты, $p_2$ --- номер второй сверху перфокарты, и так далее до перфокарты $p_n$, которая лежит ниже всех. Если возможных ответов несколько, вы можете вывести любой из них.

Если способа упорядочить перфокарты нужным образом не существует, выведите единственное число $-1$.

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