题目描述

译自 ROI 2021 Day1 T1. Перфокарты

在举办编程比赛的公司仓库里，发现了 $n$ 张打孔卡片。每张打孔卡片是一条由 $m$ 个格子组成的条带，每个格子要么包含一个小写英文字母，要么是一个孔洞。

比赛评委决定将所有打孔卡片按某种顺序排列，使得如果将它们从上到下叠放起来，就能形成比赛的口号——一个长度为 $m$ 的字符串 $s$。

换句话说，固定打孔卡片的顺序后，考虑任意位置 $i$ ($1 \le i \le m$)。那么字符串 $s$ 的第 $i$ 个字符必须与最上面一张在位置 $i$ 处包含字母的打孔卡片的第 $i$ 个字符相同。如果对于某个位置 $i$，没有任何打孔卡片在该位置包含字母，则无法形成所需的字符串 $s$。

请帮助评委确定打孔卡片的排列顺序。

上图展示了第二个样例中的卡片顺序。标出了从上面能看到的字母。

输入格式

第一行包含两个整数 $n, m\ (1 \le n, m \le 10^5)$，分别表示打孔卡片的数量和格子的数量。

第二行包含一个长度为 $m$ 的字符串 $s$，由小写英文字母组成。

接下来的 $n$ 行中，每行描述一张打孔卡片。

每个描述以一个整数 $k_i$ ($0 \le k_i \le m$) 开头，表示该打孔卡片中包含字母的格子数量。保证所有 $k_i$ 的总和不超过 $2\cdot 10^5$。

接下来是 $k_i$ 对 $a_{i,j}$ 和 $c_{i,j}$（$1 \le a_{i,j} \le m$，$c_{i,j}$ 是一个小写英文字母）的描述，表示在位置 $a_{i,j}$ 处有字母 $c_{i,j}$。其他位置是孔洞。保证每张打孔卡片中字母位置按升序排列，即对于任意 $1 \le j < k_i$，有 $a_{i,j} < a_{i,j+1}$。

输出格式

如果存在一种排列方式使得可以形成所需的字符串 $s$，输出 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$)，其中 $p_1$ 是最上面的打孔卡片的编号，$p_2$ 是第二张打孔卡片的编号，依此类推，直到最下面的打孔卡片 $p_n$。如果有多种可能的答案，可以输出任意一种。

如果不存在这样的排列方式，输出 $-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

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。