시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB43721118749.340%

문제

군꺾문자열은 군과 꺾으로 이루어진 문자열로, 복무율을 표현하는 방법 중 하나이다. 군꺾문자열 $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$을 출력한다.

예제 입력 1

1 4

예제 출력 1

GKK

예제 입력 2

5 7

예제 출력 2

-1

출처

Contest > 보라매컵 > 제5회 보라매컵 B번