题目背景

翻译自 ROI 2021 D1T1。

穿孔卡片是一条由 $m$ 个小方格组成的带状物，每个小方格要么包含一个小写英文字母，要么是一个孔洞。

题目描述

有 $n$ 张这样的穿孔卡片。给定一个长度为 $m$ 的字符串 $s$，将所有的穿孔卡片按照一定顺序排列，使得将它们从上到下依次叠放后可以变成 $s$。换句话说，要确定穿孔卡片的顺序，它们将叠放在一起，并考虑任意位置 $i(1 \le i \le m)$，字符串 $s$ 的第 $i$ 个字符必须与第 $i$ 个位置上第一个包含字母的那张穿孔卡片上的字符相同。

如果对于某个 $i$，不存在任何一个穿孔卡片上的这个位置有字母，那么就无法得到目标字符串 $s$。

输入格式

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

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

接下来的 $n$ 行中，每行输入一张穿孔卡片的信息。

先输入一个整数 $k_i(0\le k_i\le m)$，表示该穿孔卡片上有多少个带字母的位置。保证所有 $k_i$ 的总和不超过 $200,000$。

然后是该穿孔卡片上字母的描述：对于每个整数 $j(1 \le j \le k_i)$，有一个整数 $a_{i,j}$ 和一个字符 $c_{i,j}$（$1 \le a_{i,j} \le m$，$c_{i,j}$ 是一个小写英文字母），表示位置 $a_{i,j}$ 上的字符是 $c_{i,j}$。其余位置都是孔洞。保证每张穿孔卡片上的带字母的位置按升序排列，即 $\forall1 \le j < k_,a_{i,j} < a_{i,{j+1}}$。

输出格式

如果存在一种正确排列穿孔卡片的方法，输出 $n$ 个整数 $p_1,p_2,\dots,p_n(1 \le pi \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

提示

样例 $2$ 解释：

数据范围：