🍎 모열씨의 글로벌 떡국집 (Final Edition)

문제

글로벌 프랜차이즈의 수장 모열씨(Moyul-ssi)는 가게의 시그니처 마크를 살려 주문서의 단어 구분자로 사과(🍎) 이모지를 사용합니다.

손님이 주문서에 요리를 요청하면, 시스템은 각 동작 단어 사이에 정확히 🍎를 끼워 넣어 하나의 긴 문자열로 모열씨에게 전달합니다. 모열씨는 이 주문 문자열을 왼쪽부터 순서대로 읽으며 스택(Stack) 구조의 냄비를 이용해 조리를 진행합니다. 초기 상태의 냄비는 완전히 비어 있습니다.

[주문 토큰 및 조리 규칙]

주문서에서 파싱되는 단어와 조리 동작은 다음과 같습니다. 모든 단어는 🍎로 구분되어 들어옵니다.

  1. 떡국: 냄비에 완성된 떡국 요리($T$)를 하나 넣습니다. (출력 번호: 1)

  2. 만둣국: 냄비에 완성된 만둣국 요리($M$)를 하나 넣습니다. (출력 번호: 3)

  3. 떡: 현재 냄비의 가장 위가 떡국 요리($T$)라면, 떡을 꺼내고 국물만 남은 상태인 일반 떡 요리($t$)로 변환합니다. 만약 냄비가 비어있거나, 이미 일반 떡 요리($t$)이거나 만둣국 계열의 요리가 있다면 조리가 불가능합니다. (출력 번호: 2)

  4. 만두: 현재 냄비의 가장 위가 만둣국 요리($M$)라면, 만두를 꺼내고 국물만 남은 상태인 일반 만두 요리($m$)로 변환합니다. 만약 냄비가 비어있거나, 이미 일반 만두 요리($m$)이거나 떡국 계열의 요리가 있다면 조리가 불가능합니다. (출력 번호: 4)

⚠️ [불가능한 주문 (예외 처리)]

조리 도중 다음 중 하나의 상황이 발생하면, 즉시 조리를 중단하고 에러 메시지를 출력해야 합니다.

  • 냄비 상태와 맞지 않는 재료 추출 주문이 들어온 경우 (예: 떡국인데 만두를 꺼내라는 경우, 만둣국인데 떡을 꺼내라는 경우)

  • 이미 가공을 거쳐 일반 떡($t$)이나 일반 만두($m$)가 되었는데 연속해서 조리 명령이 들어오는 경우

  • 주문 문자열을 🍎 기준으로 잘랐을 때, 위의 4가지 단어(떡국, 만둣국, 떡, 만두)가 아닌 잘못된 단어가 포함되어 있거나 🍎가 올바르지 않게 연속으로 위치한 경우

입력

첫째 줄에 🍎로 구분된 주문 문자열 $S$가 주어집니다. ($1 \le |S| \le 300,000$)

출력

주문이 올바르게 수행될 수 있다면:

  • 첫째 줄에 수행한 조리 동작 번호를 공백 없이 순서대로 출력합니다.

  • 둘째 줄에 최종적으로 완성된 냄비 가장 위(Top) 요리의 영문 이름을 출력합니다. (Tteokguk, Manduguk, Rice cake, Dumpling 중 하나, 비어있다면 Empty)

주문 도중 예외가 발생하거나 잘못된 형식이면:

  • 첫째 줄에 Sorry It's Impossible을 출력합니다.

예제 입력 1

떡국🍎만둣국

예제 출력 1

13
Manduguk

예제 입력 2

떡국🍎떡

예제 출력 2

12
Rice cake

예제 입력 3

만둣국🍎떡

예제 출력 

Sorry It's Impossible

(설명: 만둣국에서는 떡을 꺼낼 수 없습니다.)

예제 입력 4

떡국🍎떡🍎만두

예제 출력 4

Sorry It's Impossible