수식 만들기

퍼즐 하나를 보자. 흔히 쓰는 수학 기호와 숫자 $4$ 네 개만으로 값이 $113$인 수식을 쓸 수 있을까?

답 하나는 다음과 같다.

$113 = \frac{\sqrt{4} + (\sqrt{4} + 4!)\%}{\sqrt{4}\%}$

여기서 !는 계승 기호이고 %는 백분율 기호다. 즉 11% = 0.11이다.

포 포스는 숫자 $4$ 네 개와 흔히 쓰는 수학 기호만으로 주어진 수를 만드는 산술 퍼즐이다. $16 = 4 + 4 + 4 + 4$처럼 쉬운 수도 있지만, 위의 $113$처럼 그렇지 않은 수도 있다. $4$ 네 개로 $2016$을 만들 수 있을까?

이 문제는 그 퍼즐의 변형이다. 두 정수 $x$와 $y$가 주어지면 다음 규칙을 지키면서 값이 $y$인 수식을 써야 한다.

• 수식에 쓸 수 있는 상수는 정수 $x$ 하나뿐이다.
• 쓸 수 있는 연산은 덧셈, 뺄셈, 곱셈, 나눗셈뿐이다.
• 수식의 연산 횟수는 $28$번 이하다.
• 중간 결과의 절댓값은 $10^{18}$을 넘지 않는다.
• 모든 나눗셈은 나누는 수가 0이 아니고 몫이 정수다.

규칙을 동시에 만족하는 수식은 여러 개다. 출력에서 그중 하나를 정하며, 그 수식을 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

다음 $T$개 줄에 각각 두 정수 $x$와 $y$가 공백을 사이에 두고 주어진다.

• $1 \le T \le 212121$
• $0 \le x, y < 1212$

각 테스트 케이스마다 한 줄을 출력한다.

수식은 x, +, -, *, / 다섯 문자로 이루어진 문자열, 곧 후위 표기식으로 쓴다. 빈 스택에서 시작해 문자열을 왼쪽부터 읽으며 계산한다.

• x는 수 $x$를 스택에 넣는다.
• +는 스택에서 두 수 $b$와 $a$를 이 순서로 꺼낸 다음 $a + b$를 넣는다.
• -는 $b$와 $a$를 꺼낸 다음 $a - b$를 넣는다.
• *는 $b$와 $a$를 꺼낸 다음 $a \times b$를 넣는다.
• /는 $b$와 $a$를 꺼낸 다음 $a / b$를 넣는다.

마지막 문자까지 읽은 뒤 스택에 수가 정확히 하나 남아야 하고, 그 수가 수식의 값이다. 연산자를 읽을 때 스택에 수가 두 개보다 적거나 끝난 뒤 수가 정확히 하나가 아니면 계산은 실패한다.

다음 규칙이 정하는 수식을 출력한다.

• $x = 0$이고 $y > 0$이면 IMPOSSIBLE을 출력한다.
• $y = 0$이면 xx-를 출력한다.
• 그 밖에는 $S(y)$ 뒤에 x/를 붙여 출력한다.

$S(n)$은 $1 \le n \le 1211$에서 정의되며, 값이 $n \times x$인 후위 표기식이다. $S(n)$에 들어 있는 문자 x의 개수를 $c(n)$이라 하자. $n = 1$의 기본 문자열은 x이므로 $c(1) = 1$이다. 나머지 문자열은 다음 세 규칙으로 만든다.

• 곱: $n = a \times b$이고 $2 \le a \le b \le 1211$이면 $S(a)$, $S(b)$, *x/를 차례로 이어 붙인다. 문자 x는 $c(a) + c(b) + 1$개다.
• 합: $n = a + b$이고 $1 \le a \le b \le 1211$이면 $S(a)$, $S(b)$, +를 차례로 이어 붙인다. 문자 x는 $c(a) + c(b)$개다.
• 차: $n = a - b$이고 $1 \le b < a \le 1211$이면 $S(a)$, $S(b)$, -를 차례로 이어 붙인다. 문자 x는 $c(a) + c(b)$개다.

$c(n)$은 이 규칙으로 만들 수 있는 문자열의 문자 x 개수 중 가장 작은 값이고, $S(n)$은 그 최솟값에 도달하는 문자열이다. 도달하는 문자열이 여럿이면 곱, 합, 차 순으로 고르고, 같은 종류 안에서는 $a$가 가장 작은 것을 고른다. 최솟값에 도달하는 문자열의 두 조각은 언제나 $c(a) < c(n)$과 $c(b) < c(n)$을 만족하므로 $S(n)$은 모든 $n$에서 하나로 정해진다.

이렇게 출력한 수식의 연산 횟수는 $28$번을 넘지 않는다.