복호화 과제

가까운 미래, 국가 안보를 이유로 암호학에 관한 모든 연구와 출판이 전 세계에서 금지된다. 암호학 문헌이 공개되어 있으면 범죄자를 포함한 누구나 그것을 이용해 자신의 계획을 당국으로부터 숨길 수 있기 때문이다. 그 결과 공개된 암호 시스템은 더 이상 존재하지 않게 되었고, 비밀을 강력하게 보호해야 하는 사람은 누구나 자체 알고리즘을 직접 만들어야 한다.

ACM 사는 자사의 영업 비밀을 알아내려는 경쟁자가 많다. 잘 보호되는 내부 회선과 달리 도청이 쉬운 대륙 간 통신 회선을 써야 하기 때문에 비밀을 지키기가 더욱 어렵다. 이에 ACM 사는 대륙 간 암호 보호 코드(Intercontinental Cryptographic Protection Code, ICPC)를 고안했고, 이를 깰 수 없다고 자부한다 — 지금까지는.

이름을 밝히지 않은 경쟁사에 고용된 해커들이 ICPC를 깨기로 한다. 이들은 먼저 ICPC를 구현한 프로그래머 한 명을 매수해 그 동작 방식을 알아냈다. ICPC는 정교한 무작위 물리 과정으로 생성한 바이트 열, 즉 매우 긴 키를 사용한다. 이 키는 매주 바뀌며, 그 주에 대륙 간 회선으로 보내는 모든 메시지를 암호화하는 데 쓰인다. ICPC가 매우 빠른 이유는 메시지의 바이트와 키 사이에 비트 단위 배타적 논리합(XOR)만 계산하기 때문이다. 즉, 암호문의 $i$번째 바이트는 $E_i = K_i \oplus C_i$이며, 여기서 $K_i$는 키의 $i$번째 바이트, $C_i$는 원본 평문의 $i$번째 바이트이다.

이제 해커들은 매주 바뀌는 키를 확실히 얻을 방법이 필요하다. 이들은 키가 바뀐 직후 직원들에게 주간 소식지를 보내는 사무원을 찾아냈다. 소식지는 충분히 길어서 평문 소식지와 그 암호문을 함께 분석하면 키의 상당 부분을 복원할 수 있다. 그러나 비밀유지계약(NDA)에 따라 사내 메시지 유출의 벌칙이 사형이므로, 어떤 직원도 소식지 내용을 넘겨주려 하지 않는다.

그래서 해커들은 (약간의 보상을 주고) 사무원에게 겉보기에는 사소한 일을 시켰다. 소식지 사본을 사내로 보낼 때, 일부 사본의 맨 앞에는 공백 문자 하나를 추가하고 다른 사본은 원래대로 보내게 한 것이다.

이제 키를 복원하는 일은 간단하며, 그 프로그램을 만드는 것이 여러분의 과제다. ICPC로 암호화된 두 메시지가 주어진다. 첫 번째 메시지는 $N$바이트이다. 두 번째 메시지는 $N+1$바이트로, 첫 번째와 같은 평문을 암호화하되 맨 앞에 공백 문자 하나(십진수 값 $32$인 바이트)를 추가한 것이다. 두 메시지를 암호화하는 데 사용된 키의 처음 $N+1$바이트를 구하라.

입력은 두 줄로 이루어진다.

• 첫 번째 줄은 $2N$개의 문자로 이루어지며, $N$바이트 길이의 첫 번째 암호문을 나타낸다.
• 두 번째 줄은 $2N+2$개의 문자로 이루어지며, $N+1$바이트 길이의 두 번째 암호문을 나타낸다.

여기서 $1 \le N \le 10000$이다. 각 메시지는 한 줄에 공백 없이 바이트 단위로 16진수로 적혀 있다. 각 바이트는 그 바이트의 16진수 값을 나타내는 두 문자 0-9, A-F로 표현된다.

복원한 키의 $N+1$바이트를 입력과 같은 16진수 형식(바이트당 대문자 16진수 두 자리, 공백 없음)으로 한 줄에 출력한다.