Андроид Андреид — известный на всю галактику детектив. Сейчас он расследует дело о мошенниках, подделывающих знаменитые шестеренки Стоппа, такую же популярную сейчас головоломку, какой был когда-то кубик Рубика.

Самыми важными ее компонентами являются кнопка и ряд из n одинаковых шестеренок. Каждая шестерёнка имеет n зубцов, на которых написаны в порядке против часовой стрелки все числа от 0 до n - 1. При нажатии кнопки первая шестеренка поворачивается по часовой стрелке, за ней поворачивается вторая шестерёнка против часовой стрелки, за ней третья по часовой стрелке и так далее.

Также у каждой шестеренки есть ровно один активный зубец. При повороте шестерёнки новым активным зубцом становится следующий за текущим активным в соответствии с направлением поворота. Например, если n = 5, а активным зубчиком является тот, на котором написано число 0, то при повороте по часовой стрелке активным станет зубчик с числом 1, а при повороте против часовой — зубчик с числом 4.

Андреид помнит, что настоящая головоломка обладает следующим свойством: можно так нажать на кнопку несколько раз, что в итоге числа на активных зубчиках шестеренок с первой по последнюю образуют последовательность 0, 1, 2, ..., n - 1. Напишите программу, определяющую, является ли данный экземпляр головоломки настоящим или поддельным.