Mihai планирует посмотреть фильм. Ему нравятся только фильмы-палиндромы, поэтому он хочет пропустить некоторые (возможно, ноль) сцен, чтобы оставшиеся части фильма образовали палиндром.
Вам дан список \(s\) из \(n\) непустых строк длины не более \(3\), представляющих сцены из фильма Mihai.
Подпоследовательность \(s\) называется классной, если она не пуста и конкатенация строк подпоследовательности по порядку является палиндромом.
Можете ли вы помочь Mihai проверить, есть ли хотя бы одна классная подпоследовательность \(s\)?
Палиндром — это строка, которая читается одинаково в обоих направлениях. Например, строки «z», «aaa», «aba», «abccba» являются палиндромами, а строки «codeforces», «reality», «ab» таковыми не являются.
Последовательность \(a\) называется непустой подпоследовательностью последовательности \(b\), если \(a\) получается из \(b\) удалением нескольких (возможно, нуля, но не всех) элементов.
Выходные данные
Для каждого набора входных данных выведите «YES», если есть классная подпоследовательность \(s\), или «NO» в противном случае (без учета регистра).
Примечание
В первом наборе входных данных из \(s\) можно выбрать классную подпоследовательность \([ab, cc, ba]\).