덧셈식이나 뺄셈식의 ?마다 숫자를 채워 등식을 성립시키고 전체 문자열이 사전 순으로 가장 작게 만듭니다.
쉬움3완전 탐색문자열수학아직 제출이 없습니다시간 제한5초메모리 제한512 MB한 출판사가 2012년 새 학기에 맞춰 초등학교 저학년용 계산 연습 문제집을 만들었다. 문제 수가 많아 학구열 높은 부모 사이에서 인기가 높았다. 이를 시기한 경쟁 출판사가 출판 직전에 원고에 손을 대 문제에 있던 숫자를 마구잡이로 지워 놓았다. 문제집이 무사히 나올 수 있도록 지워진 숫자를 찾아내자.
숫자 연산자 숫자 = 숫자 형태다.+ 또는 뺄셈 -이다.?로 표시한다.= 사이에는 공백 문자가 하나씩만 있고, 수식의 맨 앞과 맨 뒤에는 공백이 없다.첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어지는 T개의 줄에 각각 수식이 하나씩 주어지며, 숫자의 일부 자리가 ?로 지워져 있다.
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 복원한 수식이다.
복원 결과가 여러 개면 수식 전체를 하나의 문자열로 보았을 때 사전순으로 가장 작은 것을 출력한다. 예를 들어 1? - ? = 3은 10 - 7 = 3, 11 - 8 = 3, 12 - 9 = 3으로 복원할 수 있고, 이 중 사전순으로 가장 작은 10 - 7 = 3을 출력한다.