Форма Номер
В компьютерном зрении код цепочки представляет собой последовательность чисел, обозначающих направления при обходе контура объекта. Например, на следующем рисунке контур описывается кодом цепочки 22234446466001207560, начиная с верхнего левого угла.
Два кода цепочки могут описывать одну и ту же форму, если форма была повернута или если начальная точка контура выбрана иначе. Чтобы нормализовать код относительно вращения, можно вычислить первую разность кода цепочки. Первая разность определяется как количество изменений направления против часовой стрелки между последовательными элементами в коде цепочки (последний элемент считается последовательным с первым). Для приведенного выше кода первая разность равна
00110026202011676122
Чтобы нормализовать начальную точку, рассматриваются все циклические перестановки первой разности, и выбирается лексикографически наименьший код. Этот код называется номером формы.
001100262020116761220110026202011676122011002620201167612200...20011002620201167612
В данном случае 00110026202011676122 является номером формы для указанной формы.
Входные данные
Входные данные состоят из нескольких случаев. Каждый случай представлен одной строкой, содержащей код цепочки формы. Длина кода цепочки не превышает 300000, и все цифры в коде находятся в диапазоне от 0 до 7 включительно. Контур может пересекать сам себя и не обязательно возвращается к начальной точке.
Выходные данные
Для каждого случая выведите полученный номер формы после выполнения описанных нормализаций.