드라이잠 방정식

머나먼, 아마도 문명이 없었을 어느 행성의 사막 Dreisamwüste를 발굴하던 중, 알 수 없는 기호가 적힌 종이들이 발견되었다. 오랜 조사 끝에 과학자들은 이 기호들이 방정식의 일부일지도 모른다는 결론을 내렸다. 만약 그것이 사실이라면, Dreisamwüste가 아주 오래전에 문명을 이루고 있었다는 증거가 될 것이다.

문제는 종이에 적힌 기호가 숫자, 괄호, 등호뿐이라는 점이다. Dreisamwüste 사람들은 덧셈, 뺄셈, 곱셈이라는 세 가지 연산만 알고 있었다는 강력한 증거가 있다. 또한 그들에게는 연산자 우선순위 규칙이 없어서, 모든 식을 왼쪽에서 오른쪽으로 순서대로 계산했다. 그들에게 3+3*5는 18이 아니라 30이다.

지금 종이에는 연산자가 하나도 남아 있지 않다. 따라서 가설이 옳고 숫자들이 정말로 방정식을 이룬다면, 연산자는 오랜 세월에 걸쳐 사라져 버린 것이다.

당신의 임무는 사라진 연산자를 복원하는 것이다. 연산자 없이 주어진 각 방정식에 대해, +, -, *를 적절히 끼워 넣어 등식이 성립하도록 만들 수 있는지 판단하라. 예를 들어 종이에 18=7 (5 3) 2가 적혀 있다면 18=7+(5-3)*2가 하나의 해가 된다(왼쪽에서 오른쪽으로 ((7+(5-3))*2)=18로 계산된다). 그러나 5=3 3은 결코 올바른 등식으로 만들 수 없다.

각 방정식은 한 줄을 차지한다. 각 줄은 $2^{30}$ 미만의 양의 정수로 시작하고, 그 뒤에 등호 =가 온다. (Dreisamwüste 사람들은 좌변이 하나의 수인 방정식만 사용했다.) = 다음에는 우변을 이루는 최대 12개의 양의 정수가 온다. 이 수들의 곱은 $2^{30}$ 미만이다. 하나 이상의 수로 이루어진 묶음은 괄호로 감쌀 수 있으며, 괄호의 개수에는 제한이 없다. 한 줄의 길이는 80자를 넘지 않는다. 두 수 사이에는 항상 공백이나 괄호가 적어도 하나 있으며, 그 외에는 공백이 자유롭게 나타날 수 있다.

숫자 0 하나만 있는 줄이 입력의 끝을 나타내며, 이 줄은 처리하지 않는다.

각 방정식에 대해 Equation #n: 줄을 출력한다. 여기서 n은 입력에서 그 방정식이 몇 번째인지를 나타내며 1부터 시작한다. 다음 줄에는 +, -, * 기호를 끼워 넣어 완성한 등식을 공백 없이 출력한다.

같은 방정식을 성립시키는 연산자 배치가 여러 가지일 수 있으므로, 완성된 등식 문자열 중 사전순으로 가장 앞서는 것을 출력한다(바이트 단위로 비교). 숫자와 괄호의 위치는 고정되어 있으므로, 이는 왼쪽에서 오른쪽으로 각 자리에서 * < + < - 순서에 따라 가장 앞서는 연산자를 고르는 것과 같다.

어떤 방법으로도 연산자를 끼워 넣어 등식을 성립시킬 수 없다면 대신 Impossible을 출력한다.

연속한 방정식 사이에는 빈 줄을 하나 출력한다. 마지막 방정식 뒤에는 빈 줄을 출력하지 않는다.