16857번 - 잉크를 엎질렀다 서브태스크스페셜 저지

디디는 알파벳 대문자[A-Z]로 구성된 문자열 S에 대해서 S[1 ~ N]와 S의 부분 문자열 S[i ~ N]의 가장 긴 공통 접두사의 길이를 Z_i라고 했을 때, 이로 구성된 배열 Z를 빠르게 구하는 방법에 대해서 연구하고 있었다. 오랜 공부 끝에 발견한 알고리즘으로 배열 Z를 완성시킨 디디는 기쁨의 춤을 추다가 그만 문자열 S 일부에 잉크를 엎질렀다. 그래서 디디는 자신이 만든 배열 Z가 올바른 지 확인할 수 없었다. 착한 ryute는 절망한 디디를 위해 문자열 S에서 일부 문자가 가려진 문자열 S'와 디디가 작성한 배열 Z를 이용해서 원본 문자열 S를 복원해주려고 한다. 또한, 디디가 만든 배열 Z가 올바른지도 대신 확인해주려고 한다. 원본 문자열 S로 가능한 경우가 하나라도 있다면 배열 Z는 올바른 것으로 간주하고, 그렇지 않다면 올바르지 않은 것으로 간주한다. ryute를 따라서 디디를 도와주자.

첫째 줄에 문자열 S의 길이 N(1 ≤ N ≤ 10⁵)이 주어진다.

둘째 줄에 문자열 S'가 주어진다. S'는 알파벳 대문자[A-Z]와 #으로 구성되어 있다. #은 해당 글자가 잉크에 의해 가려졌다는 것을 의미하며, #의 개수는 20개를 넘지 않는다.

셋째 줄에 디디가 작성한 배열 Z의 원소 Z_i(0 ≤ Z_i ≤ N-i+1)가 순서대로 공백으로 구분되어 주어진다.

만약 디디가 만든 배열 Z가 올바르지 않다면 THINKINGFACE를 출력하라. 그렇지 않다면 첫째 줄에 YES, 둘째 줄에 원본 문자열 S를 출력하라. 만약 S로 가능한 문자열이 여러 개라면 그 중 하나를 출력하라.

1 ≤ N ≤ 3000이며, #의 개수는 1을 넘지 않는다.

1 ≤ N ≤ 3000이다.

추가적인 제약 조건이 없다.