Макс або Мін

У Кевіна є n цілих чисел a[1], a[2], ..., a[n], розташованих по колу. Це означає, що числа a[i] і a[i+1] (1 ≤ i < n) є сусідніми, а також a[1] і a[n] є сусідами. Таким чином, кожне число має рівно два сусіди.

За одну хвилину Кевін може змінити a[i] на мінімальне з трьох чисел: a[i] і двох його сусідів. Або ж він може змінити a[i] на максимальне з тих же чисел. Наприклад, якщо a[i] = 5 і його сусіди — 3 і 2, то після мінімальної операції a[i] стане 2. Якщо ж виконати максимальну операцію, a[i] залишиться 5.

Для кожного x від 1 до m знайдіть мінімальну кількість хвилин, необхідних, щоб усі числа стали рівними x, або визначте, що це неможливо.

Вхідні дані

Перша строка містить два цілих числа n і m (3 ≤ n ≤ 2 * 10^5, 1 ≤ m ≤ 2 * 10^5) — кількість чисел у колі та кількість чисел, для яких потрібно знайти відповіді.

Друга строка містить n цілих чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ m) — числа, розташовані по колу.

Вихідні дані

Виведіть m цілих чисел. i-е число повинно бути рівним мінімальній кількості хвилин, необхідних для того, щоб усі числа стали рівними i, або -1, якщо це неможливо.

Приклади

Примітка

Щоб усі числа стали рівними 2, Кевіну потрібно як мінімум 5 хвилин. Одна з можливих послідовностей операцій:

1. Виконайте операцію min для a[6], вона стане 2.

2. Виконайте операцію max для a[4], вона стане 2.

3. Виконайте операцію max для a[3], вона стане 5.

4. Виконайте операцію min для a[2], вона стане 2.

5. Виконайте операцію min для a[3], вона стане 2.