CF1685B Linguistics

Alina has discovered a weird language, which contains only $ 4 $ words: $ \texttt{A} $ , $ \texttt{B} $ , $ \texttt{AB} $ , $ \texttt{BA} $ . It also turned out that there are no spaces in this language: a sentence is written by just concatenating its words into a single string. Alina has found one such sentence $ s $ and she is curious: is it possible that it consists of precisely $ a $ words $ \texttt{A} $ , $ b $ words $ \texttt{B} $ , $ c $ words $ \texttt{AB} $ , and $ d $ words $ \texttt{BA} $ ? In other words, determine, if it's possible to concatenate these $ a+b+c+d $ words in some order so that the resulting string is $ s $ . Each of the $ a+b+c+d $ words must be used exactly once in the concatenation, but you can choose the order in which they are concatenated.

N/A

N/A

In the first test case, the sentence $ s $ is $ \texttt{B} $ . Clearly, it can't consist of a single word $ \texttt{A} $ , so the answer is $ \texttt{NO} $ . In the second test case, the sentence $ s $ is $ \texttt{AB} $ , and it's possible that it consists of a single word $ \texttt{AB} $ , so the answer is $ \texttt{YES} $ . In the third test case, the sentence $ s $ is $ \texttt{ABAB} $ , and it's possible that it consists of one word $ \texttt{A} $ , one word $ \texttt{B} $ , and one word $ \texttt{BA} $ , as $ \texttt{A} + \texttt{BA} + \texttt{B} = \texttt{ABAB} $ . In the fourth test case, the sentence $ s $ is $ \texttt{ABAAB} $ , and it's possible that it consists of one word $ \texttt{A} $ , one word $ \texttt{AB} $ , and one word $ \texttt{BA} $ , as $ \texttt{A} + \texttt{BA} + \texttt{AB} = \texttt{ABAAB} $ . In the fifth test case, the sentence $ s $ is $ \texttt{BAABBABBAA} $ , and it's possible that it consists of one word $ \texttt{A} $ , one word $ \texttt{B} $ , two words $ \texttt{AB} $ , and two words $ \texttt{BA} $ , as $ \texttt{BA} + \texttt{AB} + \texttt{B} + \texttt{AB} + \texttt{BA} + \texttt{A}= \texttt{BAABBABBAA} $ .