E. Инна и бинарная логика
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдоволь наслушавшись шуток о женской логике, Инна взяла и перешла на бинарную.

У Инны есть массив a1, состоящий из n целых неотрицательных чисел: a1[1], a1[2], ..., a1[n]. Девочка любит развивать свою бинарную логику, для этого она выполняет упражнение, которое состоит из n этапов: на первом этапе Инна выписывает все элементы массива a1, на i(i ≥ 2) этапе девочка выписывает все элементы массива ai, который состоит из n - i + 1 целых чисел и k-е число которого равно ai[k] = ai - 1[kAND ai - 1[k + 1]. Здесь операция AND обозначает операцию побитового И двух чисел.

Дима решил проверить насколько хорошо Инна выполняет описанное упражнение. Для этого он просит Инну изменять массив и после каждого изменения говорить, чему будет равна сумма чисел, которые Инна выпишет в результате выполнения упражнения над текущим массивом.

Помогите Инне ответить на все запросы Димы.

Входные данные

Первая строка входных данных содержит два целых числа n и m (1 ≤ n, m ≤ 105) — количество элементов в массиве a1 и количество запросов Димы. Следующая строка содержит n целых чисел a1[1], a1[2], ..., a1[n] (0 ≤ ai ≤ 105) — изначальные элементы массива.

В каждой из следующих m строк записана пара целых чисел — описание запросов Димы. Каждый запрос характеризуется двумя целыми числами pi, vi (1 ≤ pi ≤ n; 0 ≤ vi ≤ 105). В ответ на этот запрос Инна должна элемент a1[pi] сделать равным числу vi. Обратите внимание, изменения сохраняются от запроса к запросу.

Выходные данные

Выведите m строк. Для каждого запроса на изменение массива выведите сумму всех чисел, которые выпишет Инна, если будет выполнять упражнение над текущим массивом, в отдельной строке.

Примеры
Входные данные
3 4
1 1 1
1 1
2 2
3 2
1 2
Выходные данные
6
4
7
12