В мире Compfestnesia Пак Чанек нашел секретное подземелье. Внутри него находится сундук с сокровищами, окруженный \(n\) статуями, расположенными по кругу. Статуи пронумерованы от \(0\) до \(n-1\), причем статуя \(i\) находится слева от статуи \(i+1\), а статуя \(n-1\) — слева от статуи \(0\).
Пак Чанек заметил, что каждая статуя держит хрустальный шар с целым числом от \(0\) до \(m-1\) включительно. В хрустальном шаре статуи \(i\) содержится число \(a_i\).
В подземелье есть инструкция, согласно которой, чтобы открыть сундук с сокровищами, все целые числа в хрустальных шарах должны быть равны \(0\). Для этого Паку Чанеку дается целое число \(k\), и он может выполнить ноль или более операций. За одну операцию Пак Чанек делает следующее:
- Он выберет ровно \(k\) последовательных статуй. Другими словами, выберет статуи \(p, (p+1) \bmod n, (p+2) \bmod n, (p+3) \bmod n, \ldots, (p+k-1) \bmod n\) для некоторого выбранного индекса \(p\).
- Выполнит одно из следующих действий:
- Для каждой выбранной статуи заменит её значение \(a_i\) на \((a_i+1) \bmod m\).
- Для каждой выбранной статуи заменит её значение \(a_i\) на \((a_i-1) \bmod m\).
Помогите Паку Чанеку найти минимально возможное количество операций, чтобы открыть сундук с сокровищами.
Выходные данные
Если возможно выполнить ноль или более операций так, чтобы стало \(a_0=a_1=\ldots=a_{n-1}=0\), выведите минимальное требуемое количество операций. В противном случае выведите \(-1\).