Your internship in Team.GOV is over.
Unfortunately, we cannot make you a full-time offer.
Don't be upset, because you are neither the first nor the last one.
It was a great pleasure to work with you.
We wish you best of luck.
Vadim Kantorov, the captain of Team.GOV
A freezing November night in the year of 2010.
The dormitory of Department of Mathematics and Mechanics
of Ural State University.
Dim monitor light.
That's how Den Mukhametianov (the 8th team member in succession)
At the beginning of September Den returned from hot summer vacations.
He was calmly browsing the photos from a trip when he got an email “You are invited to an interview with Team.GOV”.
A year before Den could only dream of this.
The picture emerges in the mind as if it all had been yesterday.
It was a small cozy room, Vadik settled comfortably in a rocking chair.
Den coughed awkwardly and shitfed his feet.
Vadik looked up and smiled.
“What experience have you got?”
“Half a year in Ural SU AirBug and half a year in Ural SU Quickov.”
“Hm, not bad. What's your favorite topic?”
“Well, then straight to the point then,” Vadik interrupted Den. “Let's
pick a problem. Do you know what is Hamming distance between two strings of
“Yes, it's the number of positions on which the characters of the strings
are not equal.”
“Exactly! Let's define the distance from a pattern p to a string s as
the sum of Hamming distances from p to all substrings of s of length |p|.
In the string and in the pattern some characters are erased. You need to
recover the erased characters in such a way that the distance from p to s
The first line contains the string s, the second contains the pattern p.
Both strings are not empty and their lengths don't exceed 1000.
Strings are comprised of the following characters: “0”, “1” and “?”.
Here, “?” stands for erased characters that you need to recover.
Length of p doesn't exceed length of s.
The first line should contain the minimal distance from p to s
after all erased characters are recovered.
In the second and in the third line output s and p respectively
where each character “?” is replaced with either “0” or “1”.
Problem Author: Mikhail Rubinchik
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011