题目描述

在举办信息学奥林匹克的公司仓库里，发现了 $n$ 张打孔卡。每张打孔卡是一条由 $m$ 个格子组成的纸带，每个格子要么写有一个小写英文字母，要么是一个孔。

评测委员会希望把所有打孔卡从上到下按某种顺序叠放，使得从上方看到的字符串恰好是给定的长度为 $m$ 的字符串 $s$。

更具体地说，固定打孔卡的顺序后，对任意位置 $i(1\le i\le m)$，从最上方开始看，第一个在位置 $i$ 有字母的打孔卡，其字母必须等于 $s_i$。如果某个位置 $i$ 上所有打孔卡都是孔，则无法得到字符串 $s$。

请帮助评测委员会判断应按什么顺序叠放这些打孔卡。

展示了第二个样例中打孔卡的叠放顺序，并标出了从上方可见的字母。

输入格式

第一行包含两个整数 $n,m$，表示打孔卡数量和每张卡的格子数。

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

接下来 $n$ 行，第 $i$ 行描述第 $i$ 张打孔卡。每行先给出一个整数 $k_i$，表示这张卡上有字母的位置数。随后给出 $k_i$ 对数据 $a_{i,j},c_{i,j}$，表示位置 $a_{i,j}$ 上写有字符 $c_{i,j}$；其余位置都是孔。

对于同一张打孔卡，给出的有字母位置按升序排列，即 $a_{i,j}<a_{i,j+1}$。

输出格式

若存在合法叠放顺序，输出 $n$ 个整数 $p_1,p_2,\ldots,p_n$，其中 $p_1$ 是最上面的打孔卡编号，$p_2$ 是第二张，以此类推，$p_n$ 是最下面的打孔卡编号。

若有多种合法答案，输出任意一种即可。

若不存在合法叠放顺序，输出一个整数 -1。

数据范围

• $1\le n,m\le 100000$；
• $0\le k_i\le m$；
• $\sum k_i\le 200000$；
• $1\le a_{i,j}\le m$；
• $c_{i,j}$ 为小写英文字母。

样例

样例 1 输入

1 1
a
1 1 a

样例 1 输出

1

样例 2 输入

3 4
glhf
3 1 r 3 h 4 i
3 1 r 2 l 3 o
2 1 g 4 f

样例 2 输出

3 1 2

样例 3 输入

2 2
aa
2 1 a 2 b
2 1 b 2 a

样例 3 输出

-1

子任务