You did it! You got a coveted NSA (National Security Agency) internship because of your exceptional performance in CS211! But as you enter the office your supervisor frantically runs up to you and says that NSA needs you to solve a problem quickly. She tells you that an international criminal mastermind had been captured with n identical paper copies of a secret password (written as string of ones and zeros) that he was about to distribute to his lieutenants. But just as he was cornered by the police, he managed to rip each copy into two pieces and throw the ripped up papers out of the window. The police managed to retrieve all the papers, but the problem is that the papers were not necessarily ripped up in the same place.

Your task

Your job is to take the papers and write a program to figure out what the original sequence was. If you can do it within the next hour, you will save the world. Youre not quite sure how this will save the world, or why a time limit of an hour is specified. Out of earshot of the supervisor, the other programmers tell you that your supervisor made up the whole story to get you to solve the problem as quickly as possible. What really happened was that someone in the office pulled a prank on senior management, and changed the code on the lock of the executive bathroom. The sequence on the torn papers is the new code to the bathroom door Whatever the truth is, you still need to solve the problem. If you do it, you will be a hero; if you dont, well, your internship and recommendation might be on the line.

The input

Here are the torn papers: 011 0111 01110 111 0111 10111

Caveat

Your supervisor told you that (just in case it happens again) your program should work for any number of torn papers conforming to the story above. Go figure.