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] 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 $\text{[math]}$ 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⁵) — 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.

Output

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

Inna and Binary Logic

Examples