천공 카드

프로그래밍 올림피아드가 열리는 회사의 창고에서 천공 카드 $n$장이 발견되었다. 천공 카드는 $m$개의 칸으로 이루어진 띠이며, 각 칸에는 영소문자가 적혀 있거나 구멍이 뚫려 있다.

올림피아드 심사위원회는 모든 천공 카드를 특정 순서로 정렬하려고 한다. 이 순서대로 카드를 위에서 아래로 포개면, 길이 $m$의 주어진 문자열 $s$인 올림피아드 구호가 만들어진다.

다시 말해, 카드를 놓을 순서를 고정하고 임의의 위치 $i$ ($1 \le i \le m$)를 살펴보자. 그러면 문자열 $s$의 $i$번째 문자는 $i$번 위치에 문자가 적힌 가장 위쪽 천공 카드의 $i$번째 문자와 같아야 한다. 어떤 $i$에 대해 $i$번 위치에 문자가 있는 천공 카드가 하나도 없다면, 원하는 문자열 $s$를 만들 수 없다고 본다.

심사위원회가 천공 카드를 어떤 순서로 놓아야 하는지 알아내도록 도와라.

그림 1: 두 번째 예제의 카드 순서. 위에서 보이는 글자가 강조되어 있다

첫째 줄에는 천공 카드의 수와 칸의 수를 나타내는 두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 100\,000$).

둘째 줄에는 $m$개의 영소문자로 이루어진 문자열 $s$가 주어진다.

다음 $n$개 줄 중 $i$번째 줄에는 $i$번째 천공 카드의 정보가 주어진다.

정보는 이 카드에서 문자가 있는 위치의 수를 나타내는 정수 $k\_i$로 시작한다 ($0 \le k\_i \le m$). 모든 $k\_i$의 합은 $200\,000$을 넘지 않는다.

이어서 이 천공 카드에 있는 문자들의 정보가 주어진다. 모든 정수 $1 \leq j \leq k\_i$에 대해 $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 \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$