Aho

시간 제한1초메모리 제한512 MB

요약

숨겨진 문자열 T에 문자가 하나씩 추가될 때마다 위치 간 문자 일치 여부를 최대 5번 질문하고, T의 부분 문자열 중 S와 같은 것의 개수를 답합니다.

문제

이 문장과 이후 모든 문장에 나오는 인물과 사건은 허구이다. 실존하거나 과거에 실존했던 인물과 닮은 점이 있다면 순전한 우연이다.

이 문제는 대화형 문제이다.

Alfred와 Margaret은 커피숍 "Donald's place"에서 즐거운 저녁을 보낼 때마다 이상한 문자열 맞추기 게임을 한다.

이번 게임의 규칙은 다음과 같다.

첫 번째 플레이어는 미리 정해진 길이 $N$ 의 문자열 $S$ 를 적는다. 첫 번째 플레이어는 처음에 비어 있는 문자열 $T$ 도 가진다. 두 문자열 모두 영어 소문자로만 이루어진다.
두 번째 플레이어는 게임 내내 이 문자열들을 볼 수 없다. 다만 어느 문자열이든 임의의 두 위치의 문자가 같은지 물어볼 수 있다. 예를 들어 "문자열 $S$ 의 두 번째 문자와 문자열 $T$ 의 다섯 번째 문자가 같은가?"와 같이 묻는다. 같은 문자열의 두 위치를 비교하는 질문도 허용된다.
게임은 $M$ 라운드로 진행된다. 각 라운드를 시작할 때 첫 번째 플레이어는 문자열 $T$ 의 끝에 문자 하나를 덧붙인다.
문자가 새로 추가되면 두 번째 플레이어는 질문을 최대 5개까지 할 수 있다. 그다음 두 번째 플레이어는 $T$ 의 부분 문자열 중 $S$ 와 같은 것이 몇 개인지 말해야 한다.

Margaret은 Alfred가 두 번째 플레이어일 때 항상 성공한다는 것을 금방 알아챘다. 그녀는 $S$ 와 $T$ 가 어떤 문자열이든 두 번째 플레이어가 이길 수 있는 전략이 있다고 짐작한다. 그 전략을 찾을 수 있겠는가?

예제 1

입력

3 7
No
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes

예상 출력

s 1 s 2
s 1 s 3
s 2 t 1
s 1 t 1
$ 0
s 2 t 2
$ 0
s 3 t 3
$ 1
s 2 t 4
s 1 t 4
$ 1
s 1 t 5
$ 1
s 2 t 6
$ 1
s 3 t 7
$ 2