18162번 - Adler32 서브태스크스페셜 저지

키파는 파일 분석이 취미입니다. 키파는 오늘도 파일을 분석하다가 특정 부분의 데이터가 adler32라는 알고리즘을 통해 무결성 검사를 한다는 것을 알게 되었습니다.

adler32는 임의 길이의 데이터를 받아 4바이트의 데이터를 돌려 주는 알고리즘인데, 다음과 같이 작동합니다.

1. A := a, B := 0으로 초기화합니다.
2. 데이터의 모든 문자 c에 대해, A := A + c, B := A + B를 계산합니다.
3. 하위 16비트는 A를 p로 나눈 나머지, 상위 16비트는 B를 p로 나눈 나머지가 됩니다. (p는 65521로 고정된 소수입니다.)

Python 등의 언어에서는 from zlib import adler32; adler32(data, a) 등의 코드로 테스트해 볼 수 있습니다. 주어지는 a 값에 따라 알고리즘이 내어 놓는 수치가 조금 다릅니다. 이 알고리즘을 신기하다고 느낀 키파는 모든 데이터의 adler32를 a = 0과 a = 1인 두 가지 방법으로 저장해 놓았습니다.

그런데 키파의 친한 친구인 Kenny가 데이터를 실수로 파괴해 버렸습니다! 키파는 adler32 결과가 있으니 데이터를 복구할 수 있다고 생각했습니다. 데이터는 모두 알파벳 소문자로만 이루어져 있었다고 할 때, 키파를 위해 데이터를 복구하는 프로그램을 작성해 줍시다!

첫 줄에 adler32의 두 가지 결과, a = 0인 경우와 a = 1인 경우가 공백을 사이에 두고 주어집니다. 주어지는 수는 0 이상 2³² 미만입니다.

주어진 adler32 결과값을 갖는 알파벳 소문자로만 이루어진 문자열 데이터를 출력합니다. 그러한 것이 없으면 -1을 출력합니다.

그러한 것이 여러 개 있으면 가장 짧은 것을 출력합니다. 그러한 가장 짧은 것이 여러 개 있으면 아무거나 출력해도 됩니다.

출력하는 문자열의 길이는 1 이상이어야 합니다.

출력 문자열의 길이는 5 이하입니다.

주어지는 adler32 결과값을 갖는 알파벳 소문자로만 이루어진 문자열 데이터가 반드시 존재함이 보장됩니다. 또, 가능한 출력 문자열 중 하나는 다음 두 성질을 모두 만족합니다:

• 길이가 6·10⁴보다 작습니다.
• 문자열의 각 문자는 모두 같습니다.

추가 제약 조건이 없습니다.

"하위 16비트"는 최하위 비트(Least Significant Bit)를 포함하는, 가장 낮은 자리의 16비트를 의미합니다. 반대로, "상위 16비트"는 최상위 비트(Most Significant Bit)를 포함하는, 가장 높은 자리의 16비트를 의미합니다.