문자열 처리

MBI가 설계한 새 프로세서에는 문자열을 다루는 별도의 보조 프로세서가 있다. 이 보조 프로세서에는 소문자 라틴 알파벳으로 이루어진 문자열과 그 문자열의 처리 과정을 기술한 프로그램을 넘길 수 있다. 그러면 프로세서가 잠시 계산한 뒤 1초의 몇 분의 1만에 문자열 처리 결과를 돌려준다.

아직 개발이 끝나지 않아서 지금은 문자열을 한 가지 방식으로만 처리할 수 있다. 입력으로 넘기는 문자열은 $2^k$개의 문자로 이루어져야 하고, 그 문자열을 처리하는 프로그램은 $2^k - 1$개의 수로 이루어져야 하며, 각 수는 0 또는 1이다.

보조 프로세서에 넘긴 문자열이 한 문자로 이루어져 있다면 처리 결과는 그 문자열 자신이다. 문자열이 더 길면 다음 과정을 거친다.

먼저 문자열을 길이가 같은 두 부분으로, 프로그램을 세 부분으로 나눈다. 이때 프로그램의 처음 두 부분의 길이는 서로 같고, 세 번째 부분은 프로그램의 마지막 수 하나이다. 그다음 문자열의 앞 절반은 프로그램의 첫 부분으로 처리한 결과로, 뒤 절반은 프로그램의 두 번째 부분으로 처리한 결과로 바뀐다. 그 뒤 남은 수가 0이면 뒤 절반을 앞 절반의 오른쪽에 이어 붙이고, 1이면 앞 절반을 뒤 절반의 오른쪽에 이어 붙인다.

예를 들어 보조 프로세서에 문자열 abcd와 프로그램 $(0, 1, 1)$을 넘기면 처리 결과는 문자열 dcab이다.

여러분에게 이 프로세서의 테스트에 참여하자는 제안이 들어왔다. 이 영광스러운 제안을 거절하지 못했으므로, 이제 보조 프로세서가 문자열 $S$를 문자열 $T$로 바꾸도록 하는 프로그램을 만드는 방법을 익히거나, 그런 프로그램이 존재하지 않음을 판별해야 한다.

첫째 줄에는 정수 $n$이 하나 주어진다. 이는 분석해야 할 경우의 수이다. 다음 줄들에 $n$개의 경우가 주어진다.

각 경우의 첫째 줄에는 소문자 라틴 알파벳으로만 이루어진 문자열 $S$가 주어진다. 문자열 $S$의 길이는 $2^k$이며 $1 \le k \le 16$이다. 각 경우의 둘째 줄에는 역시 소문자 라틴 알파벳으로만 이루어진 문자열 $T$가 주어진다. 문자열 $T$의 길이는 문자열 $S$의 길이와 같다.

한 입력 파일에서 모든 문자열 $S$의 길이 합은 $100\,000$을 넘지 않는다.

각 경우마다, 문자열 $S$를 문자열 $T$로 바꾸는 보조 프로세서용 프로그램이 존재하면 출력 파일의 해당 줄에 Yes를, 존재하지 않으면 No를 출력한다.

답이 Yes이면 다음 줄에 그 변환을 위해 보조 프로세서에 넘겨야 하는 프로그램인 $2^k - 1$개의 수를 공백으로 구분해 출력한다. 그러한 프로그램이 여러 개라면 아무거나 하나 출력한다.