В наши дни средства массовой информации распространяют много слухов. Однажды Аида захотела узнать, как создаются слухи.

Она попросила n своих друзей помочь ей. Все друзья собрались в круг и Аида поведала человеку справа от неё некоторую новость, представленную простой строкой. Затем каждый человек пересказал строку человеку справа. Однако они не пересказали строку в том самом виде, в каком слышали её: каждый человек произвел не более чем одну из приведенных ниже двух видов операций:

• удалил один символа с конца услышанной строки,
• добавил один символ в конец услышанной строки.

В итоге, когда слух был пересказан ровно n раз (то есть прошел один полный круг), Аида услышала совсем не то, что ожидала услышать от человека слева. Она считает, что кто-то сжульничал и произвел изменения, отличные от изменений, приведенных выше. Теперь она хочет, чтобы вы проверили, возможно ли что строка пришедшая к ней получена по описанным выше правилам.