Перфокарты
На складе фирмы, на базе которой проходит олимпиада по программированию, были обнаружены \(n\) перфокарт. Перфокарта представляет собой полоску из \(m\) клеточек, каждая из которых либо содержит строчную английскую букву, либо является отверстием.
Жюри олимпиады решило упорядочить все перфокарты так, что если расположить их одну под другой сверху вниз в этом порядке, то получится лозунг олимпиады — заданная строка \(s\) длины \(m\).
Иными словами, зафиксируем порядок перфокарт, в котором они будут лежать, и рассмотрим произвольную позицию \(i\) (\(1 \le i \le m\)). Тогда \(i\)-й символ строки \(s\) должен совпадать с символом на \(i\)-й позиции самой верхней перфокарты, содержащей на позиции \(i\) какую-либо букву. Если для какого-то \(i\) ни одной перфокарты с буквой в позиции \(i\) нет, то считается, что требуемую строку \(s\) получить невозможно.
Помогите жюри понять, в каком порядке необходимо расположить перфокарты.
Первая строка содержит два целых числа \(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\) | \(m\) | Необходимые подзадачи | Информация о проверке |
| 1 | 15 | \(n \le 8\) | \(m \le 100\) | У | первая ошибка |
| 2 | 35 | \(n \le 100\) | \(m \le 100\) | У, 1 | первая ошибка |
| 3 | 50 | \(n \le 100\,000\) | \(m \le 100\,000\) | У, 1, 2 | первая ошибка |
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