34408번 - 문자열 분해기

문제

어느 날 윤수는 실험실에서 문자열 분해 기법을 개발해냈다. 문자열 분해는 원본 문자열을 아래 과정에 따라 결과 문자열로 만드는 기법이다.

1. 주어진 문자열에서 임의의 부분 문자열을 선택한다.
2. 선택한 부분 문자열을 원본 문자열에서 제거한 후, 문자열이 남아있다면 남은 문자열을 이어 붙인다. 이때, 제거되는 부분 문자열은 버리거나 결과 문자열의 맨 뒤에 연결할 수 있다.
3. 원본 문자열이 남지 않을 때까지 1-2 과정을 반복한다.

문자열 분해기는 문자열이 주어졌을 때 그 문자열에 대해 문자열 분해 기법을 사용한다. 당신은 윤수가 만든 문자열 분해기의 작동 결과가 올바른지 확인해 줄 것을 요청받았다. 원본 문자열 $S$와 결과 문자열 $T$가 각각 주어졌을 때, 문자열 $S$에 문자열 분해를 실행하여 문자열 $T$를 만들 수 있는지 확인해 보자.

입력

첫 번째 줄에 원본 문자열 $S$가 주어진다.

두 번째 줄에 결과 문자열 $T$가 주어진다.

문자열 $S$와 $T$는 알파벳 대문자로만 구성되어 있으며, 두 문자열 각각의 길이는 1ドル$보다 크거나 같고 10ドル,000円$을 넘지 않는다.

출력

원본 문자열 $S$에 문자열 분해를 실행하여 결과 문자열 $T$를 만들 수 있다면 OK를, 그렇지 않다면 NEED FIX를 출력한다.

제한

노트

부분 문자열이란 문자열의 연속된 일부를 의미한다. 문자열 ABC에서 A, B, C, AB, BC, ABC는 모두 문자열 ABC의 부분 문자열이다.