암호 해독

주기적 순열(periodic permutation)은 간단한 암호화 기법이다. 먼저 주기 $k$와 앞의 $k$개 위치에 대한 순열 하나를 정한다. 메시지를 암호화하려면 문자를 $k$개씩 묶고(마지막 묶음이 모자라면 채움 문자로 채운다) 각 묶음을 이 순열에 따라 재배열한다. 복호화는 문자를 $k$개씩 묶은 뒤 역순열을 적용하면 된다.

예를 들어 $k = 4$이고 순열이 2431이면 Mary는 yMra로 암호화된다. 같은 순열을 Maryan(Mary + an??로 채운 것)에 적용하면 yMra?a?n이 되며, 여기서 ?는 채움 문자를 나타낸다.

순열을 알아내면 같은 방식으로 만들어진 어떤 암호문이든 역순열을 적용하여 원문을 복원할 수 있다.

(평문, 암호문1, 암호문2) 세 쌍을 읽어, 각 (평문, 암호문1) 쌍에 대해 주기적 순열로 평문이 암호문1로 바뀔 수 있는지 판단하는 프로그램을 작성하라. 가능하다면 주기 $k$와 순열을 찾은 뒤, 그 역순열을 암호문2에 적용하여 암호문2의 평문을 복원한다.

입력은 (평문, 암호문1, 암호문2) 세 쌍의 나열이며, 한 줄에 문자열 하나씩 주어진다. 각 줄의 길이는 80자를 넘지 않는다. 한 세 쌍에서 처음 두 문자열은 길이가 같은 $n$이며, 평문과 암호문의 처음 $n$개 문자를 나타낸다. $n$이 $k$의 배수라는 보장은 없다. 입력은 # 한 글자만 있는 줄로 끝난다.

각 세 쌍마다 한 줄을 출력한다. 평문과 암호문1 문자열의 길이 이하인 주기를 갖는 주기적 순열이 평문을 암호문1로 바꿀 수 있다면, 그 역순열을 암호문2에 적용하고 필요하면 ?로 채워 결과를 출력한다. 그런 순열이 없으면 암호문2를 그대로 출력한다. 여러 주기가 가능하면 가장 작은 주기 $k$를 사용하며, 가장 작은 주기에서는 조건을 만족하는 순열이 항상 유일하다.