Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Inna and Binary Logic

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputInna is fed up with jokes about female logic. So she started using binary logic instead.

Inna has an array of *n* elements *a*_{1}[1], *a*_{1}[2], ..., *a*_{1}[*n*]. Girl likes to train in her binary logic, so she does an exercise consisting of *n* stages: on the first stage Inna writes out all numbers from array *a*_{1}, on the *i*-th (*i* ≥ 2) stage girl writes all elements of array *a*_{i}, which consists of *n* - *i* + 1 integers; the *k*-th integer of array *a*_{i} is defined as follows: *a*_{i}[*k*] = *a*_{i - 1}[*k*] *AND* *a*_{i - 1}[*k* + 1]. Here AND is bit-wise binary logical operation.

Dima decided to check Inna's skill. He asks Inna to change array, perform the exercise and say the sum of all elements she wrote out during the current exercise.

Help Inna to answer the questions!

Input

The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 10^{5}) — size of array *a*_{1} and number of Dima's questions. Next line contains *n* integers *a*_{1}[1], *a*_{1}[2], ..., *a*_{1}[*n*] (0 ≤ *a*_{i} ≤ 10^{5}) — initial array elements.

Each of next *m* lines contains two integers — Dima's question description. Each question consists of two integers *p*_{i}, *v*_{i} (1 ≤ *p*_{i} ≤ *n*; 0 ≤ *v*_{i} ≤ 10^{5}). For this question Inna should make *a*_{1}[*p*_{i}] equals *v*_{i}, and then perform the exercise. Please, note that changes are saved from question to question.

Output

For each question print Inna's answer on a single line.

Examples

Input

3 4

1 1 1

1 1

2 2

3 2

1 2

Output

6

4

7

12

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/08/2020 17:20:08 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|