수학

사바나에서도 수학 없이는 살아갈 수 없다. 좋은 사바나의 왕이 되려면 힘과 민첩함뿐 아니라 자원을 적절히 나눌 줄 알아야 하고, 그러려면 덧셈, 곱셈, 나눗셈이 필요하다. 무파사도 이를 알았기에 어느 날 심바에게 수학책을 읽게 했다. 책은 매우 어려웠고, 심바는 그중에서도 ^ 기호가 가장 어려웠다.

이 책에서 ^ 기호는 전혀 다른 두 가지 의미로 쓰인다. 하나는 거듭제곱이고, 다른 하나는 각주다. 각주는 책 끝에 실린 본문 설명을 가리키는 참조다. 이 책에서 각 ^ 뒤에는 자연수가 오고, 그 뒤에는 문장부호(마침표, 쉼표, 콜론, 물음표) 또는 공백이 온다. 심바는 각주에서 ^ 뒤에 오는 번호가 연속된 자연수라는 것을 안다. 첫 번째 각주의 번호는 1이다. 각 ^ 기호는 거듭제곱이거나 각주 중 하나이다.

가능한 모든 분류 가운데 각주의 개수가 최대인 분류만 올바른 분류로 본다.

심바는 각 ^ 기호가 올바른 분류 중 어느 하나에서 거듭제곱일 수 있는지, 그리고 어느 하나에서 각주일 수 있는지를 알고 싶어 한다.

첫 번째이자 유일한 줄에 책의 본문이 주어진다. 본문은 최대 $10^6$ 글자이며, 영문 소문자와 대문자, 숫자, ^ 기호, 마침표, 쉼표, 물음표, 공백, 콜론으로 이루어질 수 있다. 각 ^ 뒤에는 자연수(매우 큰 수일 수도 있다)가 오고, 그 수 뒤에는 공백 또는 문장부호(마침표, 쉼표, 콜론, 물음표)가 온다고 보장된다.

첫 줄에는 본문에 있는 ^ 기호의 개수를 출력한다. 둘째 줄에는 각 ^ 기호에 대해 거듭제곱일 수 있으면 Y, 아니면 N을 출력한다. 셋째 줄에는 각 ^ 기호에 대해 각주일 수 있으면 Y, 아니면 N을 출력한다.

^ 앞에 있는 문자들은 그 ^ 기호가 각주인지 거듭제곱인지에 영향을 주지 않는다.