Smallest Number With No Adjacent Duplicates

You are given a string s containing "1", "2", "3" and "?". Given that you can replace any “?” with "1", "2" or "3", return the smallest number you can make as a string such that no two adjacent digits are the same.

Constraints

• n ≤ 100,000 where n is the length of s

https://binarysearch.com/problems/Smallest-Number-With-No-Adjacent-Duplicates

Examples

Example 1

Input

• s = 3?2??

Output

• answer = 31212

Example 2

Input

• s = ???

Output

• answer = 121

Solution