eolymp
bolt
Try our new interface for solving problems
Problems

Казак Ус и НОД

Казак Ус и НОД

Time limit 2 seconds
Memory limit 256 MiB

Казак Ус получил массив a из n целых чисел. Затем Казаку рассказали о существовании массива b который также состоит из n целых чисел, однако из каких именно Ус не знает. Для нахождения массива b Казак может любое количество раз использовать следующую операцию:

  • Выбрать два целых числа 1 \leq l \leq r \leq n.

  • Узнать сумму b_l + b_{l + 1} + \dots + b_r.

  • Заплатить gcd(a_l, a_{l+1}, ..., a_r) копеек, где gcd — наибольший общий делитель (например gcd(3, 5) = 1, а gcd(15, 30, 6) = 3).

Ус просит Вас найти минимальное количество копеек, необходимое для нахождения массива b.

Затем Казак q раз изменит определенное число a_i на x. После каждого такого изменения необходимо найти минимальное количество копеек для обновленного массива.

Input data

Первая строка содержит два целых числа n и q(1 \leq n \leq 10^5, 0 \leq q \leq 10^5) — количество элементов массива a и количество изменений массива.

Вторая строка содержит n целых чисел a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9) — элементы массива.

Следующие q строк содержат по два целых числа i и x(1 \leq i \leq n, 1 \leq x \leq 10^9) — индекс элемента массива который меняют и число на которое меняют.

Output data

Выведите q + 1 число — для каждой версии массива a найдите минимальное количество копеек необходимое для нахождения массива b

Первое число — ответ исходного массива a.

Следующие q чисел — ответы для каждого обновления массива

Examples

Input example #1
5 3
20 40 9 25 15
3 10
5 21
4 135
Output example #1
5
25
9
11
Input example #2
4 2
20 4 8 36
1 2
4 18
Output example #2
16
8
8

Scoring

  1. (8 баллов): n \le 10^2, q = 0;

  2. (7 баллов): n \le 10^3, q = 0;

  3. (11 баллов): q = 0;

  4. (12 баллов): q \leq 100;

  5. (9 баллов): q \leq 500;

  6. (23 балла): q \leq 10000;

  7. (30 баллов): без дополнительных ограничений.

Author Mark Grishechkin
Source 2021 Ukrainian Olympiad in Informatics, Stage IV, Round II