덧셈

당신의 임무는 간단하다. 두 수를 더하는 것이다. 하지만 그것만으로는 너무 쉬우므로, 조금 복잡하게 만들어 보았다.

PAScript는 새로운 스크립트 언어이다. 이 언어의 스크립트는 $k$개의 줄로 이루어지며, $i$번째 줄에는 출력 가능한 ASCII 문자(코드 $33$부터 $126$까지)로 구성된 두 개의 비어 있지 않은 단어 $a_i, b_i$가 들어 있다. PAScript 인터프리터는 입력에서 문자열 $s$를 읽고 다음 의사코드를 실행한다.

while true:
  foundReplacement = false
  for i = 1, 2, ..., k:
    if a(i) is a substring of s:
    	  replace the leftmost occurrence of a(i) with b(i)
      foundReplacement = true
      break
  if not foundReplacement:
    break
	print(s)

당신의 임무는 두 이진수를 더하는 효과적인 스크립트를 찾는 것이다. 스크립트의 입력은 binary number + binary number 형태의 문자열이며, 공백과 앞의 0은 없다. 올바른 입력의 예로 10001+1001이 있다. 두 이진수는 음이 아닌 정수를 나타낸다. 입력 문자열의 길이는 $100$을 넘지 않는다.

스크립트는 입력 두 수의 합을 이진수로, 역시 앞의 0 없이 출력해야 한다. 위 예에서 결과는 11010이다.

스크립트는 짧고 효과적이어야 한다. 구체적으로 다음 조건을 만족해야 한다.

• $k \le 50$ (스크립트는 $50$줄을 넘을 수 없다);
• $1 \le |a_i|, |b_i| \le 8$ (스크립트의 어떤 단어도 $8$자를 넘거나 비어 있을 수 없다);
• 각 입력에 대해 인터프리터는 바깥쪽 while 루프를 최대 $100\,000$번 실행한다. 또한 스크립트가 실행되는 동안 $s$의 길이는 항상 $2017$자를 넘지 않는다.

이 문제에는 입력이 없다.

출력의 첫 줄에는 스크립트의 줄 수를 나타내는 하나의 수 $k$ ($1 \le k \le 50$)가 들어가야 한다. 다음 $k$개의 줄 중 $i$번째 줄은 스크립트의 $i$번째 줄을 나타내며, 하나의 공백으로 구분된 두 개의 비어 있지 않은 단어 $a_i, b_i$가 들어가야 한다.

물론 위의 예시 스크립트는 위에 제시된 문제를 해결하지 못한다. 반면 예시 스크립트는 0과 1만으로 이루어진 문자열에 대해 $1$이 적어도 하나 들어 있는지 판별한다.