Fix the Text

Time limit1sMemory limit1024 MB

Summary

Restore each # in a text to its original character, including the letter's case, using the surrounding characters as context.

Level: Medium4 of 10
Topics: String, String matching
Solved: No attempts yet

Problem

The input is an English text in which some characters have been replaced with #. Restore the text by filling in the characters that should have been at those positions.

Input

The input is a single line made of the characters a-z, A-Z, 0-9, the punctuation marks .,-:;!?"', and spaces. Some of these characters have been replaced with #. No test file has more than $500\,000$ characters. The input may contain newlines, but none of them are replaced with #.

Output

Print the input text with every # replaced by the original character at that position. Changing any character other than # makes you fail that test case. Any character may have been replaced, including spaces and punctuation. If you restore a letter, its case must also be correct. Newlines can be printed however you like, since they are ignored when checking (they do not have to match the newlines in the input).

Examples1

Example 1

Input

MAR#EY was dead: to begin with. The#e is no doubt whate##r
about#that. T#e register of his bu#ial was signe# by the
clerg#man, the cl#rk, the u#dertaker, an# the chief mou#ner.
Scrooge s#gned it: and Scr#oge's name was g#od upon 'Ch#nge,
for anyt#ing he chose to#put his h#nd#to. Old Ma##ey wa# ##
dead as#a door-nail. #Mind! I d#n't mean##o say that I#know,
of my ow##k#owledge, #hat there is #articular#y dead ab##t a
door-nail. I#might have bee# inclined, myself, to #egard a
coff#n-nail as the ##adest piec# of ironmonge#y in the
t#ade. But the#wisdom of#our ancestors is#in the simile; a#d
my unhallowed#hands shall n#t disturb i#, or the Country's
done fo## You will therefor# permit me to re#eat,
emphat#cally, that Marle# was as dead #s a doo#-#ail.

Expected output

MARLEY was dead: to begin with. There is no doubt whatever
about that. The register of his burial was signed by the
clergyman, the clerk, the undertaker, and the chief mourner.
Scrooge signed it: and Scrooge's name was good upon 'Change,
for anything he chose to put his hand to. Old Marley was as
dead as a door-nail.  Mind! I don't mean to say that I know,
of my own knowledge, what there is particularly dead about a
door-nail. I might have been inclined, myself, to regard a
coffin-nail as the deadest piece of ironmongery in the
trade. But the wisdom of our ancestors is in the simile; and
my unhallowed hands shall not disturb it, or the Country's
done for. You will therefore permit me to repeat,
emphatically, that Marley was as dead as a door-nail.