Bitwise Party

The new year has come and just like all the competitive programmers, our hero Stefan received an array with positive integers as a Christmas present as well! Now he wants to explore the array and to find new interesting properties as he always likes doing.

Task

For this year, he wants to find out the maximum number of values we can take from the array such that both the bitwise AND and the bitwise XOR are different from $0$.

Since this is too easy for him, he also modifies his array and wants you to answer to the same question after each update.

Input data

The input contains $n$, the number of integers from the array and $q$, the number of queries.

The next line contains $n$ integers, representing the numbers from Stefan's array.

The next $q$ lines contain the queries. Each query is represented by two integers, $pos$ and $val$, representing that on the position $pos$, we will change its value to $val$.

Output data

The output will contain $q+1$ lines. On the first line you will print the answer before any updates, and on the next $q$ lines you will print the answer after each update.

Constraints and clarifications

• $1 \leq n, q \leq 2 \cdot 10^5$
• $1 \leq v_i, val < 2^{20}$
• For tests worth $10$ points, $1 \leq v_i, val \leq 2$.
• For tests worth $20$ more points, $1 \leq n, q, val, v_i < 2^7$.
• For tests worth $20$ more points, $1 \leq n, q, val, v_i < 2^{10}$.

Example 1

stdin

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

stdout

3
3
4
5
4
3
4
3
4