| Codeforces Round 234 (Div. 2) |
|---|
| Закончено |
Вдоволь наслушавшись шуток о женской логике, Инна взяла и перешла на бинарную.
У Инны есть массив a1, состоящий из n целых неотрицательных чисел: a1[1], a1[2], ..., a1[n]. Девочка любит развивать свою бинарную логику, для этого она выполняет упражнение, которое состоит из n этапов: на первом этапе Инна выписывает все элементы массива a1, на i-м (i ≥ 2) этапе девочка выписывает все элементы массива ai, который состоит из n - i + 1 целых чисел и k-е число которого равно ai[k] = ai - 1[k] AND 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
