#2332 NetworkXZeroOne

19  1 s   128 MB  

Description

 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.

 

Input

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.

Output

For each test case, you program must print a single line of the form:

Sample Input

Sample Output

5
x?x?
?xo?
xo
o??x??o
???????x
xoxo
oxox
xo
oxoxoxo
oxoxoxox

Source

TopCoder Single Round Match 516 Round 1 - Division II, Level One