시간 제한
메모리 제한
시간 제한
2초
메모리 제한
128 MB
영식이와 민식이는 케이크를 나누어 먹는다. 케이크가 남아 있는 동안, 차례가 된 사람은 항상 남은 케이크의 절반을 먹는다.
두 사람이 영식, 민식 순서로 번갈아 먹는다면 영식이는 다음 양을 먹는다.
| 영식 | 민식 |
|---|---|
| 1/2 | 1/4 |
| 1/8 | 1/16 |
| 1/32 | 1/64 |
| 1/128 | 1/256 |
| ... | ... |
이 경우 영식이가 먹는 양은 전체 케이크의 2/3이고, 민식이는 1/3을 먹는다.
이제 두 사람은 정해진 패턴을 계속 반복하며 케이크를 먹으려고 한다. 패턴의 각 글자는 한 번의 차례를 뜻하며, 패턴이 끝나면 처음부터 다시 반복한다. 영식이는 *, 민식이는 -로 나타낸다.
반복되는 패턴이 영식, 민식, 영식이라면 먹는 양은 다음과 같이 진행된다.
| 영식 | 민식 | 영식 |
|---|---|---|
| 1/2 | 1/4 | 1/8 |
| 1/16 | 1/32 | 1/64 |
| 1/128 | 1/256 | 1/512 |
| ... | ... | ... |
이 패턴에서 영식이가 먹는 양은 전체 케이크의 5/7이다.
영식이가 먹어야 하는 전체 케이크의 양이 기약분수 a/b로 주어진다. 영식이가 정확히 그만큼 먹게 되는 가장 짧은 반복 패턴을 구하시오.
첫째 줄에 두 정수 a와 b가 주어진다. a와 b는 기약분수 a/b의 분자와 분모이다.
첫째 줄에 먹는 패턴을 출력한다. 패턴에서 영식이의 차례는 *, 민식이의 차례는 -로 출력한다.
길이가 60 이하인 패턴이 없다면 -1을 출력한다. 가능한 패턴이 여러 개라면 가장 짧은 것을 출력한다.
0 <= a <= b <= 2^63 - 1a와 b는 서로소이다.