In the near future any research and publications about cryptography are
outlawed throughout the world on the grounds of national security concerns.
The reasoning for this is clear and widely accepted by all governments -
if cryptography literature is public like in the old times, then everybody
(even criminals and terrorists) could easily use it to hide their
malicious plans from the national and international security forces.
Consequently, public cryptographic algorithms and systems have ceased to
exist, and everybody who needs strong protection for their secrets is forced
to invent proprietary algorithms.
The ACM Corporation has lots of competitors who are eager to learn its
trade secrets. Moreover, the job to protect their secrets is complicated by
the fact, that they are forced to use intercontinental communication lines
which are easy to eavesdrop on, unlike internal lines of the ACM Corporation
which are well guarded. Therefore, the ACM Corporation have invented the
Intercontinental Cryptographic Protection Code (ICPC) which they are very
proud of, and which is considered unbreakable - nobody has even tried to
break it yet, but that is about to change.
The group of hackers was hired by the rival company, which does not disclose
its name to them, to break ICPC. As the first step, they have bribed one of the
programmers who implemented the software for ICPC and have learned how ICPC works.
It turns out, the ICPC uses very long key which is a sequence of bytes generated
by some sophisticated and random physical process. This key is changed weekly and
is used to encrypt all messages that are sent over intercontinental communication
lines during the week. This programmer has also proudly told them, that ICPC is
the fastest code in the world, because (having the benefit of highly sophisticated
code generation) they simply perform bitwise exclusive OR (XOR) operation between
the bytes of the message and the key. That is, the ith byte of the encrypted
message Ei = Ki XOR Ci, where Ki is the
ith byte of the key and Ci is the ith byte of the
original clear-text message.
Having learned how ICPC works, they have started to look for the way to reliably
obtain the key every week, which is the only thing that is still missing to
listen for all intercontinental communications of the ACM Corporation
(eavesdropping on the intercontinental lines themselves has indeed turned out to
be an easy task). An attempt to bribe the security officers who guard and
distribute the key has failed, because the security officers (having the
profession with one the highest salaries of that time) have turned out to be
too expensive to bribe.
During the search for alternative solutions, they have stumbled upon a clerk,
who sends weekly newsletters to various employees and departments. Fortunately,
these newsletters are being sent just after the change of the key and the messages
are usually long enough to recover sufficient portions of the key by studying
original newsletters and their encoded forms. However, they could not
covertly find anyone who will disclose the newsletter contents on a weekly basis,
because all the employees were bound by a Non-Disclosure Agreement (NDA) and the
penalty for the disclosure of any corporate message according to this NDA is death.
Yet they were able to convince this clerk (for a small reward) to do a seemingly
innocent thing. That is, while sending the copies of newsletter throughout the
corporation, he was instructed to insert an extra space character in the beginning
of some messages but send other copies in their original form. Now the task to
recover the key is straightforward and it is you, who shall create a program
for this. The program is given two ICPCed messages where the first message
is N bytes, and the second one is N+1 bytes and is the result of encoding the
same clear-text messages as the first one, but with one extra space character
(represented by the byte with the decimal value of 32) in the beginning. The
program shall find the first N+1 bytes of the key that was used to encode
The input consists of two lines. The first line consists of 2N characters and
represents the encoded message N bytes long. The second line consists of 2N+2 characters
and represents the encoded message N+1 bytes long.
Here 1 ≤ N ≤ 10000. Each message is written
on a single line in a hexadecimal form byte by byte without spaces.
Each byte of the message is represented by two characters '0'-'9', 'A'-'F'
that represent the hexadecimal value of the corresponding byte.
Write a single line that represents N+1 bytes of the
recovered key in the same hexadecimal format as in the input.
Problem Author: Elena Kruchkova
Problem Source: 2002-2003 ACM Northeastern European Regional Programming Contest