Тривіально? Ріши

Вам задано масив цілих чисел $a_1,a_2,\dots ,a_n$. Ваша задача — обробити $q$ запитів:

• додати до всіх елементів масиву ціле число $x$.

Після кожного запиту виведіть найбільший спільний дільник всіх елементів масиву.

Вхідні дані

Перший рядок містить два цілі числа $n$, $q$ ($1\le n,q\le 2\cdot 10^5$) — розмір масиву та кількість запитів відповідно.

Другий рядок містить $n$ цілих чисел $a_1,\dots ,a_n$ ($1\le a_i\le 10^9$) — елементи масиву $a$.

Кожен з наступних $q$ рядків містить по одному цілому числу $x$ ($1\le x\le 10^9$).

Вихідні дані

Виведіть $q$ чисел — найбільший спільний дільник елементів масиву після кожного додавання.

Приклади

Примітка

Після першого запиту $a=[2,10,18]$ через те, що до кожного елементу додали $1$. Найбільший спільний дільник у ньому $2$.

Після другого запиту $a=[4,12,20]$ через те, що до кожного елементу додали $2$. Найбільший спільний дільник у ньому $4$.

Після третього запиту $a=[8,16,24]$ через те, що до кожного елементу додали $4$. Найбільший спільний дільник у ньому $8$.

Оцінювання

У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.

1. ($5$ балів): $a_1=a_2=\cdots =a_n$;

2. ($15$ балів): $n,q\le 1000$;

3. ($40$ балів): кількість різних елементів серед $a_1,\dots ,a_n$ не більше за $100$;

4. ($40$ балів): без додаткових обмежень.