Задано число \textbf{n} и последовательность из \textbf{n} чисел. Требуется рассмотреть все возможные циклические сдвиги заданной последовательности, отсортировать их в лексикографическом порядке и вывести согласно этому порядку. В случае равенства двух различных циклических сдвигов меньшим считается сдвиг, начинающийся левее. \InputFile Входной файл содержит не более \textbf{200} тестовых примеров. Каждый тестовый пример состоит из двух строк. Первая из них содержит целое число \textbf{1} ≤ \textbf{n} ≤ \textbf{50000} - длина последовательности. Вторая строка содержит \textbf{n} чисел в интервале от \textbf{0} до \textbf{100} - заданную последовательность. После последнего тестового примера вместо числа \textbf{n} идет \textbf{0}. \OutputFile Для каждого тестового примера выведите одно число - искомую сумму.