해커

브루노는 단어를 수로 바꾸려고 롤링 해시를 쓴다.

알고리즘은 이렇게 동작한다.

1. 해시를 $0$에서 시작한다.
2. 문자열의 문자를 앞에서부터 하나씩 보면서, 현재 해시에 $P$를 곱하고 그 문자의 알파벳 순번($1$부터 $26$까지)을 더한다.
3. 이렇게 얻은 값을 $M$으로 나눈 나머지가 최종 해시다.

이반은 영어 소문자로만 이루어진 길이 $N$짜리 문자열을 사전순으로 모두 적은 목록을 구했다. 그런데 종이가 찢어져서 문자열 $S$로 시작해 $\texttt{zz...z}$로 끝나는 부분만 남았다.

이반은 남은 목록에서 해시가 같은 서로 다른 문자열 $K$개를 찾으려 한다. 브루노의 알고리즘을 망가뜨리려는 이반의 계획을 도와라.

첫째 줄에 문제에서 설명한 자연수 $P$, $M$이 주어진다. ($1 \le P, M \le 100000$)

둘째 줄에 목록에 있는 문자열의 길이 $N$이 주어진다. ($1 \le N \le 100000$)

셋째 줄에 남은 목록의 첫 문자열 $S$가 주어진다. 길이는 $N$이고 영어 소문자로만 이루어져 있다.

넷째 줄에 이반이 원하는 문자열의 개수 $K$가 주어진다. ($1 \le K \le 20$)

답은 다음 규칙으로 하나로 정한다. 남은 목록을 $S$부터 사전순으로 훑어보면서, 문자열 $t$까지 봤을 때 $S$부터 $t$까지 중 해시가 $t$와 같은 문자열이 처음으로 $K$개가 되면 거기서 멈춘다. 이때 해시가 $t$와 같은 그 $K$개를 사전순으로 한 줄에 하나씩 출력한다. 마지막 줄은 $t$가 된다.

목록 끝까지 가도 해시가 같은 문자열이 $K$개인 값이 없으면 $\texttt{NEMOGUCE}$ 한 단어만 출력한다.