Tidy up my bit string I have a series of binary switches, which I can represent as a bit string. The last person who used my switches left them in some arbitrary state without cleaning up, and it bugs me. I always keep the switches in one of four possible "tidy" configurations:


All 1: e.g., 111111111
All 0: e.g., 000000000
Alternating 1 and 0: e.g., 10101010 or 01010101


However, in addition to being fastidious about my switch arrangements, I'm also very lazy, and want to extend the smallest amount of effort possible to reset the switches to one of my preferred states.

Challenge

Write a program or function that takes a sequence of ones and zeros of any length. It should output a result of the same length that shows the closest "tidy" configuration.

Input and output


You may represent your bit sequence using a string or any language-native ordered type, such as a list or array. If using a non-string structure, items within the sequence may be number or string representations of 1 and 0.


Your strings may have leading and trailing characters like "..." or [...]

Your input and output formats are not required to match. (For example, you may input a list and output a string.)
Don't input or output base 10 (or other base) representations of the bit string. That's way too much effort to correspond back to switches -- I'm doing this because I'm lazy, remember?
Output must be a sequence as specified above. Don't output an enumerated value saying which of the four configurations is the best (e.g., don't say, "solution is case #3"). Actually output a bit sequence in that configuration.
Input may be of any length. Your code may not impose arbitrary limits on the size of the input.


If your language or interpreter imposes reasonable arbitrary limits on the size of an input or call stack (e.g, if you choose a recursive solution), then this is acceptable insofar as it is a shortcoming in your environment, not your code.



Notes


The distance between two strings is the Hamming distance. You must find the "tidy" configuration of the same length at the input that has the fewest number of differences from the input.
If multiple tidy configurations are equally best choices, you may output any best choice, or (at your option) multiple best choices, delimited in some way or as siblings in a data structure. The selection can be completely arbitrary and does not need to be consistent between executions.
The input might already be a tidy state.


Examples

Input:  1111110
Output: 1111111

Input:  001010000
Output: 000000000

Input:          0010100
Allowed output: 0000000
Allowed output: 1010101
[You may choose either allowed output, or both]

Input:  1111
Output: 1111

Input:  10
Output: 10

Input:  010101101
Output: 010101010

Input:          110
Allowed output: 111
Allowed output: 010
Python 2, 127 103 101 bytes



lambda a:min(zip(*[[1,0,i%2,~-i%2]for i in range(len(a))]),key=lambda N:sum(o^b for o,b in zip(a,N)))


Try it online!

Makes the lists 111..., 000..., 101... and 010... with the first zip then finds the min of these lists with key function: sum of the xor of each element in the each possible output the input.