19 1 s 128 MB
Toastman has sent Fox Ciel a message consisting entirely of lowercase 'o' and 'x' letters. This message has the interesting property that for any even-length contiguous substring of this message, the number of 'o's will equal the number of 'x's.
Unfortunately due to the nature of the network, some of the letters in the message can become corrupted. You are given a String message, each character of which is 'o', 'x', or '?'. 'o' or 'x' denotes that the letter in the message is not corrupted and is equal to the corresponding letter. A '?' denotes that the letter at that position is corrupted and might have been either 'o' or 'x'.
Your job is to replace each of the '?' characters in the input by either 'o' or 'x' such that the resulting message has the interesting property described above, and print that corrected message.
First line, a number of test cases T( T <= 50)
Next line, message
message will contain between 2 and 50 characters, inclusive.
Each character in message will be lowercase 'o', lowercase 'x', or '?'. At least one('o', 'x' ) is present in message.
There will be exactly one possible corrected message which has the interesting property described in the problem statement.
For each test case, you program must print a single line of the form:
5 x?x? ?xo? xo o??x??o ???????x
xoxo oxox xo oxoxoxo oxoxoxox