Задана строка \(a\), состоящая из \(n\) символов, \(n\) четно. Для каждого \(i\) от \(1\) до \(n\) \(a_i\) является одним из 'A', 'B' или 'C'.
Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов '1' и '+'. Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.
Вы хотите найти такую строку \(b\), которая состоит из \(n\) символов, что:
- \(b\) является правильной скобочной последовательностью;
- если для некоторых \(i\) и \(j\) (\(1 \le i, j \le n\)) \(a_i=a_j\), тогда \(b_i=b_j\).
Другими словами, вы хотите заменить все вхождения 'A' скобками одного типа, затем все вхождения 'B' скобками одного типа и все вхождения 'C' скобками одного типа.
Ваша задача — определить, существует ли такая строка \(b\).
Выходные данные
Для каждого набора входных данных выведите «YES», если существует такая строка \(b\), что:
- \(b\) является правильной скобочной последовательностью;
- если для некоторых \(i\) и \(j\) (\(1 \le i, j \le n\)) \(a_i=a_j\), тогда \(b_i=b_j\).
Иначе выведите «NO».
Вы можете вывести каждую букву в любом регистре (например, YES, Yes, yes, yEs будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных одна из возможных строк \(b\) равна «(())()».
Во втором наборе входных данных одна из возможных строк \(b\) равна «()()».