디지털 XOR

시간 제한1초메모리 제한1024 MB

요약

각 자릿수가 1부터 9인 N이 주어질 때, 7세그먼트 불빛 상태의 XOR로 N을 만들고 합이 가장 작은 두 개 이상의 피연산자 조합을 구한다.

난이도: 보통10점 중 7점
유형: 비트 연산, 구현, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

평소에 주식시장에 관심이 많은 우영이는 한국거래소 메인 홀에 있는 시황판의 디지털 다이얼에 빠져들게 되었다. 우영이는 자신이 갖고 있던 채권의 가격이 계속 떨어지는 것도 모른 채 다음과 같이 디지털 XOR의 정의를 내렸다.

Definition 1. 디지털 XOR의 피연산자는 자릿수가 같은 다이얼 상의 상태이며, 이 상태는 각 자리의 7개의 불빛이 켜져 있거나 꺼져 있는 경우로 표현된다.

Definition 2. 아래 예시와 같이, 디지털 XOR의 연산 결과는 피연산자들과 자릿수가 같으며, 각 피연산자의 대응되는 위치의 불빛이 홀수 개 켜져 있는 경우 해당 위치의 불빛이 켜진 상태가, 짝수 개 켜져 있는 경우 꺼진 상태가 된다.

우영이는 문득, 두 개 이상의 피연산자들을 디지털 XOR 했을 때의 연산 결과가 특정한 양의 정수 $N$ 이 되는 경우가 있을지 살펴보기 시작했다. 여기서 우영이는 아래와 같이 자신만의 규칙을 만들었다.

모든 피연산자들과 최종 연산 결과 $N$ 은 모두 아래 그림과 같이, $1$ 부터 $9$ 까지를 표현한 다이얼 상의 상태로 이루어져 있다. $0$ 은 포함되어 있지 않다.
피연산자의 길이 이하의 임의의 양의 정수 $i$ 에 대해서, 모든 피연산자들의 $i$ 번째 자릿수는 모두 같거나, 모두 다르다.

우영이는 위 조건을 만족하는 피연산자의 조합이 여러 개가 존재할 수 있음을 발견하고, 다음과 같은 추가 규칙을 작성했다.

1번과 2번 조건을 만족하는 피연산자의 조합이 여러 개인 경우, 그 중 합이 가장 작은 것을 선정한다.
1번, 2번, 3번 조건을 만족하는 피연산자의 조합이 여러 개인 경우, 그 중 곱이 가장 작은 것을 선정한다.

우영이을 도와, 디지털 XOR을 하여 양의 정수 $N$ 이 되는 피연산자의 조합을 구해보자.

입력

첫 번째 줄에 정수 $N$ ( $1 \le N \le 10^{10000} - 1$ )이 주어진다. $N$ 의 각 자릿수는 모두 $0$ 이 아니다.

출력

문제의 조건을 만족하는 2개 이상의 피연산자의 조합이 존재하는 경우, 첫 번째 줄에 그 수들의 합과 사용된 피연산자의 개수를 공백으로 구분하여 출력하고, 두 번째 줄부터 각 줄마다 피연산자들을 작은 것부터 순서대로 하나씩 출력한다. 조건을 만족하는 정답이 여러 개일 경우 아무거나 출력한다.

문제의 조건을 만족하는 2개 이상의 피연산자의 조합이 존재하지 않는 경우, 첫 줄에 $-1$ 을 출력한다.

예제3

예제 1
입력
```
11
```
예상 출력
```
33 3
11
11
11
```
예제 2
입력
```
51
```
예상 출력
```
153 3
51
51
51
```
예제 3
입력
```
53
```
예상 출력
```
156 4
11
22
35
88
```