Вам надано масив цілих чисел \(A=(a_1,a_2,\ldots,a_N)\). Ви можете виконати наступну операцію будь-яку кількість разів (можливо, нуль).

• Виберіть непорожній суміжний підмасив \(A\) та видаліть його з масиву.

Для кожного \(x=1,2,\ldots,M\) розв’яжіть таку задачу:

• Знайдіть мінімально можливу кількість операцій, щоб сума елементів \(A\) дорівнювала \(x\). Якщо неможливо зробити так, щоб сума елементів \(A\) дорівнювала \(x\), то виведіть -1.

Зверніть увагу, що сума елементів порожнього масиву дорівнює 0.

Обмеження

• \(1 \leq N,M \leq 3000\)
• \(1 \leq A_i \leq 3000\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N, M\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть М рядків. У \(i\)-му рядку має бути відповідь на \(x=i\).

Приклад вхідних даних

4 5
1 2 3 4

Приклад вихідних даних

1
2
1
1
1

Приклад вхідних даних

1 5
3

Приклад вихідних даних

-1
-1
0
-1
-1

Приклад вхідних даних

12 20
2 5 6 5 2 1 7 9 7 2 5 5

Приклад вихідних даних

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1