34620번 - 군꺾문자열

문제

군꺾문자열은 군과 꺾으로 이루어진 문자열로, 복무율을 표현하는 방법 중 하나이다. 군꺾문자열 $S$가 표현하는 복무율의 값은 다음과 같이 계산한다.

• 초기 상태에서 $x = 0$이다.
• $S$를 차례대로 읽으면서 군이면 $x$에 1ドル$을 더하고, 꺾이면 $x$를 2ドル$로 나눈다.
• 모든 글자를 읽은 후 $x$의 값이 $S$가 표현하는 복무율이다.

예를 들어, 군꺾문자열 군꺾군군꺾꺾꺾이 표현하는 복무율 $x$를 계산하는 과정은 다음과 같다.

1. 군 → $x = 1$
2. 꺾 → $x = \frac{1}{2}$
3. 군 → $x = \frac{3}{2}$
4. 군 → $x = \frac{5}{2}$
5. 꺾 → $x = \frac{5}{4}$
6. 꺾 → $x = \frac{5}{8}$
7. 꺾 → $x = \frac{5}{16}$

따라서 군꺾군군꺾꺾꺾은 $\frac{5}{16}$의 복무율을 표현한다.

하늘이의 현재 복무율을 뜻하는 기약분수 $\frac{a}{b}$가 주어진다. 이를 정확히 표현하는 가장 짧은 군꺾문자열을 구하여라. 만약 $\frac{a}{b}$를 표현하는 가장 짧은 군꺾문자열이 여러 개라면 그 중 사전순으로 가장 빠른 것을 구하여라.

만약 하늘이의 복무율 $\frac{a}{b}$를 어떤 군꺾문자열로도 표현할 수 없다면 $-1$을 출력한다.

입력

첫째 줄에 정수 $a, b$가 공백을 사이에 두고 주어진다. (1ドル \leq a < b \leq 10^9,ドル $a$와 $b$는 서로소)

출력

첫째 줄에 $\frac{a}{b}$를 표현하는 가장 짧은 군꺾문자열을 출력한다. 만약 $\frac{a}{b}$를 표현하는 가장 짧은 군꺾문자열이 여러 개라면 그 중 사전순으로 가장 빠른 것을 출력한다. 이때 군은 G, 꺾은 K로 출력한다.

만약 하늘이의 복무율 $\frac{a}{b}$를 군꺾문자열로 표현할 수 없다면 첫째 줄에 $-1$을 출력한다.

제한

노트