Counting Valid XOR Pairs with Updates

You are given a sequence \(a\) of length \(n\) and \(q\) update operations. Initially, you are given \(a_1, a_2, \ldots, a_n\). For each operation, you must perform the following steps:

1. Change \(a_x\) to \(y\).
2. After this update, compute the number of valid pairs \((a_i, a_j)\) with \(i \max\{a_i,a_j\}, \] where \(\oplus\) denotes the bitwise XOR operation and \(\max\{a_i,a_j\}\) is the maximum of \(a_i\) and \(a_j\).

Note: It can be proved that for any pair \((a_i,a_j)\) (with \(i a_j\) holds if and only if both \(a_i\) and \(a_j\) are nonzero and \(a_i\) and \(a_j\) do not share any common set bit (i.e. \(a_i \& a_j = 0\)).

Your task is to process the queries and output the count of valid pairs after each update operation.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 2000)\), representing the length of the sequence and the number of queries respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) where \(0 \le a_i \le 10^9\).

Each of the next \(q\) lines contains two integers \(x\) and \(y\) \((1 \le x \le n, 0 \le y \le 10^9)\) representing an update: change \(a_x\) to \(y\).

outputFormat

After each query, output a single integer on a new line representing the number of valid pairs in the current array.

sample

4 3
1 2 3 4
2 4
3 0
1 2

4
2
2