Mihai планирует посмотреть фильм. Ему нравятся только фильмы-палиндромы, поэтому он хочет пропустить некоторые (возможно, ноль) сцен, чтобы оставшиеся части фильма образовали палиндром.

Вам дан список $$$s$$$ из $$$n$$$ непустых строк длины не более $$$3$$$, представляющих сцены из фильма Mihai.

Подпоследовательность $$$s$$$ называется классной, если она не пуста и конкатенация строк подпоследовательности по порядку является палиндромом.

Можете ли вы помочь Mihai проверить, есть ли хотя бы одна классная подпоследовательность $$$s$$$?

Палиндром — это строка, которая читается одинаково в обоих направлениях. Например, строки «z», «aaa», «aba», «abccba» являются палиндромами, а строки «codeforces», «reality», «ab» таковыми не являются.

Последовательность $$$a$$$ называется непустой подпоследовательностью последовательности $$$b$$$, если $$$a$$$ получается из $$$b$$$ удалением нескольких (возможно, нуля, но не всех) элементов.