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

Inna has an array of n elements a₁[1],a₁[2],...,a₁[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₁, 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]ANDa_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!

The first line contains two integers n and m (1≤n,m≤10⁵) − size of array a₁ and number of Dima's questions. Next line contains n integers a₁[1],a₁[2],...,a₁[n] (0≤a_i≤10⁵) − 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⁵). For this question Inna should make a₁[p_i] equals v_i, and then perform the exercise. Please, note that changes are saved from question to question.

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