편집 거리

이진 문자열은 0과 1로 이루어진 공백이 아닌 수열이다. 예를 들어 $010110$, $1$, $11101$ 등이 있다. 두 이진 문자열 $S$와 $T$의 편집 거리 $\text{edit}(S, T)$는 $S$를 $T$로 바꾸는 데 필요한 최소 한 글자 편집(삽입, 삭제, 치환) 횟수이다. 예를 들어 $0011$과 $1100$의 편집 거리는 $4$이다. 즉 $0011 \to 011 \to 11 \to 110 \to 1100$ 순서로 바꿀 수 있다. $1100101$과 $1110100$의 편집 거리는 $2$이다. 즉 $1100101 \to 1110101 \to 1110100$ 순서로 바꿀 수 있다.

아유에게 이진 문자열 $S$가 있다. 그녀는 $S$와 길이가 같으면서 $S$와의 편집 거리가 최대가 되는 이진 문자열을 찾고 싶어 한다. 형식적으로 말하면, $|S| = |T_{\max}|$이고, $|S| = |T'|$를 만족하는 모든 이진 문자열 $T'$에 대해 $\text{edit}(S, T_{\max}) \ge \text{edit}(S, T')$가 성립하는 이진 문자열 $T_{\max}$를 찾는 것이다.

그녀는 당신의 도움이 필요하다. 다만 과제를 쉽게 만들어 주고 싶어 하니, $S$와 길이가 같은 이진 문자열 $T$ 중 $S$와의 편집 거리가 $S$ 길이의 절반보다 큰 것이면 아무거나 출력해도 된다. 형식적으로는 $|S| = |T|$이고 $\text{edit}(S, T) > |S|/2$인 이진 문자열 $T$를 출력해야 한다.

물론 $T_{\max}$를 출력해도 된다. 어떤 이진 문자열 $S$에 대해서도 $\text{edit}(S, T_{\max}) > |S|/2$임이 증명되어 있기 때문이다. 이는 모든 $S$에 대해 해가 존재함을 보여 준다. 유효한 해가 여러 개라면 그중 아무거나 출력하면 된다.

입력은 이진 문자열 $S$($1 \le |S| \le 2000$)이다.

한 줄에 $S$와 길이가 같은 이진 문자열 $T$를 출력한다. $T$는 $\text{edit}(S, T) > |S|/2$를 만족해야 한다.