어디로 가야 할까요?

"리오카드는 리오에서만 되는 거야??" (두두, 2014년)

두두는 타이어를 전혀 모른다. 그래서 고향인 브라질 리우데자네이루를 떠나 타이 방콕으로 가기 전에, 자주 쓸 만한 문장을 종이에 적어 두었다.

대부분은 평범한 인사말이었다. "사왓디" (안녕하세요), "폼 츄 두두" (제 이름은 두두입니다), "호 워크라프 콩 폼 뎀빠이두어이 쁠라 라이" (제 호버크라프트가 장어로 가득합니다) 같은 것이다.

거기에 타이 문자로 적은 문장 하나를 더 준비했다. "도와주세요. 저는 관광객이고 타이어를 못 합니다. 룸피니 지하철역에 가려면 어떤 열차를 타야 하는지 알려 주세요."

방콕에 도착한 두두는 두 번 놀랐다. 리오카드를 쓸 수 없었고, 글자도 라틴 문자가 아니었다. "안녕하세요"마저 สวัสดี처럼 적혀 있었다.

길을 잃고 호텔로 돌아가려던 두두는 큰 "도와주세요" 쪽지를 꺼내며 생각했다. "이 쪽지 어딘가에 내가 갈 역 이름이 적혀 있어. 역 이름 목록 전체가 있으면 그 이름이 타이 문자로 어떻게 적히는지 알아낼 수 있을지도 몰라."

쪽지는 대문자 알파벳으로 이루어진 문자열 $s$로 주어지고, 역 이름은 각각 소문자 알파벳 문자열로 주어진다. 두 표기 모두 타이 문자를 알파벳으로 대신 적은 것이지만 서로 다른 규칙을 쓰므로, 역 이름의 글자와 $s$의 글자를 직접 견줄 수는 없다. 견줄 수 있는 것은 모양뿐이다.

길이가 $m$인 역 이름이 $s$의 위치 $j$에 나타날 수 있다는 것은, 그 이름의 글자와 부분문자열 $s_j s_{j+1} \dots s_{j+m-1}$의 글자를 일대일로 대응시켜서 이름의 같은 글자가 $s$의 같은 글자 위에 오고 이름의 서로 다른 글자가 $s$의 서로 다른 글자 위에 오도록 만들 수 있다는 뜻이다.

예를 들어 역 이름이 abla라면 타이 문자로는 네 글자이고, 첫 글자와 넷째 글자가 같으며 둘째와 셋째는 서로 다르고 첫 글자와도 다르다. 두두가 역을 찾도록 도와주자.

첫째 줄에 지하철 역의 개수 $N$이 주어진다.

둘째 줄에 두두가 준비한 문장 $s$가 주어진다.

다음 $N$개의 줄에 역 이름이 한 줄에 하나씩 주어진다.

• $1 \le N \le 1000$
• $1 \le |s| \le 1000$

역 이름은 빈 문자열이 아니고, 모든 역 이름의 길이를 더한 값은 1000을 넘지 않는다.

$s$는 대문자 알파벳으로만 이루어져 있다. 역 이름은 모두 소문자 알파벳으로만 이루어져 있고, 이 소문자가 타이 문자를 나타낸다.

역 이름마다 한 줄씩, 모두 $N$개의 줄을 출력한다.

$i$번째 줄에는 $i$번째 역 이름이 $s$ 안에 있을 수 없으면 -만 출력하고, 있을 수 있으면 그 이름이 나타날 수 있는 가장 앞 위치를 수 하나로 출력한다.

$s$의 첫 글자 위치는 0이다.

역 이름의 길이가 $|s|$보다 크면 그 이름은 절대 나타날 수 없다.

글자 하나로 된 이름은 언제나 위치 0에서 맞는다. 같은 글자가 두 번 이어지는 이름은 $s$에도 같은 글자가 두 번 이어지는 곳이 있어야 맞는다. 서로 다른 글자 $k$개로 이루어진 이름은 $s$에서 서로 다른 글자 $k$개로 이루어진 길이 $k$의 구간을 찾아야 맞는다.