Description

Now I understand very clearly what people were really looking for when they sought teachers of virtue in the past.
They were looking for sleep, and poppies that help with sleep!

Zarathustra listens to a wise man on the lectern talking about the virtue of sleep. He feels bored, so he observes the boys who are listening together.

He finds that the boys’ clothes are very strange. Specifically, the clothes have $60$ kinds of features. The value of the $i$-th feature is $2^{i-1}$.

Each time he observes two boys. If there is a clothing feature that appears on only one of the two boys, and not on the other, Zarathustra’s obsessive-compulsive disorder acts up, and he gains a disgust value equal to that feature’s value.

He wants to arrange the boys into several groups such that, in each group, no matter which two boys he picks, he will get a disgust value of $<x$. Zarathustra calls such a group good.

Sometimes he also puts one boy into a group alone; in that case, no matter what, the group is good.

He wants to know: at most, how many boys can a group that satisfies the condition contain?

Sometimes a boy will go home and change clothes. When he comes back, his clothing features may change.

Input Format

The first line of the input contains three integers $n,q,x$, representing the number of boys, the number of times boys go home to change clothes, and the threshold.

The next line contains $n$ integers $a_1,a_2,\dots,a_n$, where $a_i$ is the sum of the feature values of the $i$-th boy’s clothing at the beginning.

The next $q$ lines each contain two integers $ind,val$, meaning the boy with index $ind$ has just come back after changing clothes, and the sum of his clothing feature values becomes $val$.

Output Format

Output $q+1$ lines, each containing one non-negative integer.

The number on line $i$ is the answer before the $i$-th modification.

The number on line $q+1$ is the answer after all modifications are finished.

10 10 4
6 10 1 1 6 9 0 5 3 0 
3 5
1 10
9 3
8 10
3 0
8 11
1 3
1 4
2 8
1 0

5
4
4
4
4
5
5
6
5
5
6

Hint

For $20\%$ of the data, $n\le 20$.

For $30\%$ of the data, $n\le 1000$.

For $50\%$ of the data, $n\le 50000$.

For another $20\%$ of the data, $x$ is an integer power of $2$.

For $80\%$ of the data, $q=0$.

For $100\%$ of the data, $1\le ind\le n\le 100000,0\le q\le 100000,0\le x,a_i,val< 2^{60}$.

Translated by ChatGPT 5