많은 LCS

정수 $K$가 주어진다. 가장 긴 공통 부분 수열(LCS)의 서로 다른 경우가 정확히 $K$개가 되도록, 길이가 8848 이하인 비어 있지 않은 이진 문자열 $S$와 $T$를 만들어라. 보다 정확히는, $L$을 $S$와 $T$의 최장 공통 부분 수열 길이라 할 때, $S$와 $T$의 부분 수열이면서 길이가 $L$인 서로 다른 이진 문자열이 정확히 $K$개 존재해야 한다.

이 문제의 제약 조건에서는 그러한 문자열이 항상 존재하는 것이 보장된다.

입력은 한 줄이며, 정수 $K$($1 \le K \le 10^9$)가 주어진다.

비어 있지 않은 이진 문자열 $S$와 $T$를 각각 한 줄에 출력한다. 두 문자열의 길이는 각각 8848을 넘지 않아야 하며, 서로 길이가 달라도 된다.

답이 여러 개이면 그중 아무거나 출력해도 된다.

첫 번째 예제에서 1111과 00의 최장 공통 부분 수열 길이는 0이다. 길이가 0인 부분 수열은 빈 문자열 하나뿐이다.

두 번째 예제에서 10과 01의 최장 공통 부분 수열 길이는 1이고, $S$와 $T$의 공통 부분 수열 중 길이가 1인 것은 0과 1 두 개이다.

세 번째 예제에서 010과 1001의 최장 공통 부분 수열 길이는 2이고, 길이가 2인 공통 부분 수열은 00, 01, 10 세 개이다.

문자열을 에베레스트보다 길게 만드는 것은 예의가 아니다...