Background

Every day, CT only hums the blues in London and wanders around in front of the school leaders. This lazy and carefree life makes him very down, so he decides to turn over a new leaf and study mathematics.

Problem Description

CT is working on a math problem.

CT has a sequence $a$ of length $n$. Now $q$ operations are given. For each operation:

• Change $a_x$ to $y$.
• After the modification, find the number of valid ordered pairs in the array.

Note: For a pair $(a_i, a_j)$ with $i < j$ that satisfies $a_i \oplus a_j > \max\{a_i, a_j\}$, we call it a valid pair. Here $\oplus$ denotes bitwise XOR, and $\max\{x, y\}$ denotes the larger one of $x$ and $y$.

Input Format

The first line contains two integers $n, q$.

The second line contains $n$ integers, representing the sequence $a$.

The next $q$ lines each contain two integers $x, y$, representing an operation that changes $a_x$ to $y$.

Output Format

For each operation:

Output one integer representing the required answer.

6 4
1 1 4 5 1 4
1 2
4 3
5 2
6 5

9
10
10
9

Hint

Constraints

For all testdata, it is guaranteed that $1 \le n \le 10^6$, $1 \le q \le 10^5$, $1 \le a_i \le 10^6$, $1 \le x \le n$, $1 \le y \le 10^6$.

Translated by ChatGPT 5