캐리 없는 덧셈

시간 제한2초메모리 제한512 MB

요약

n개의 이진수 a_i가 주어질 때, 각 b_i가 a_i 이상이고 두 b_i가 같은 자리에 1을 갖지 않도록 골라 합을 최소로 만드는 값을 이진수로 출력합니다.

난이도: 어려움10점 중 9점
유형: 그리디, 비트 연산
정답자: 아직 제출이 없습니다

문제

드물게 비트별 '또는'(OR) 연산을 2진수로 표현된 양의 정수의 덧셈 대신 쓸 수 있다. 어떤 자리에서든 1을 갖는 수가 집합에 최대 하나뿐이라면, 집합의 합은 비트별 또는 연산의 결과와 같다. 이런 집합을 아름다운 집합이라고 하자.

비트별 또는 연산은 다음과 같이 정의된다. 결과의 각 자리는 집합의 수 중 하나라도 그 자리가 1이면 1이 된다.

양의 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다. 모든 $i$ ( $1 \le i \le n$ )에 대해 $b_i \ge a_i$ 를 만족하는 양의 정수 아름다운 집합 $b_1, b_2, \ldots, b_n$ 을 만들어, 합 $b_1+b_2+\ldots+b_n$ 이 최소가 되게 하라.

$a_1, \ldots, a_n$ 의 2진 표현을 입력받아, 그러한 아름다운 집합 합의 최솟값을 2진 표현으로 출력하는 프로그램을 작성하라.

입력

첫째 줄에 집합의 원소 개수 $n$ 이 주어진다 ( $2 \le n \le 300000$ ). 다음 $n$ 개의 줄에는 양의 정수 $a_i$ 의 2진 표현이 한 줄에 하나씩 주어진다. 각 표현에는 앞자리 0이 없으며, 모든 표현 길이의 합은 300000을 넘지 않는다.

출력

아름다운 집합 $b_1, b_2, \ldots, b_n$ 의 합의 최솟값을 2진 표현으로 출력한다. 앞자리 0은 출력하지 않는다.

예제3

예제 1
입력
```
2
10
10
```
예상 출력
```
110
```
예제 2
입력
```
2
10100
1001
```
예상 출력
```
11101
```
예제 3
입력
```
3
1
1
110
```
예상 출력
```
1011
```