CF1889A Qingshan Loves Strings 2

Qingshan has a string $ s $ which only contains $ \texttt{0} $ and $ \texttt{1} $ . A string $ a $ of length $ k $ is good if and only if - $ a_i \ne a_{k-i+1} $ for all $ i=1,2,\ldots,k $ . For Div. 2 contestants, note that this condition is different from the condition in problem B. For example, $ \texttt{10} $ , $ \texttt{1010} $ , $ \texttt{111000} $ are good, while $ \texttt{11} $ , $ \texttt{101} $ , $ \texttt{001} $ , $ \texttt{001100} $ are not good. Qingshan wants to make $ s $ good. To do this, she can do the following operation at most $ 300 $ times (possibly, zero): - insert $ \texttt{01} $ to any position of $ s $ (getting a new $ s $ ). Please tell Qingshan if it is possible to make $ s $ good. If it is possible, print a sequence of operations that makes $ s $ good.

N/A

N/A

In the first test case, you can do zero operations and get $ s=\texttt{01} $ , which is good. Another valid solution is to do one operation: (the inserted $ \texttt{01} $ is underlined) 1. $ \texttt{0}\underline{\texttt{01}}\texttt{1} $ and get $ s = \texttt{0011} $ , which is good. In the second and the third test case, it is impossible to make $ s $ good. In the fourth test case, you can do two operations: 1. $ \texttt{001110}\underline{\texttt{01}} $ 2. $ \texttt{0011100}\underline{\texttt{01}}\texttt{1} $ and get $ s = \texttt{0011100011} $ , which is good.