Перфокарты

На складе фирмы, на базе которой проходит олимпиада по программированию, были обнаружены $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$