题目描述

现在我很清楚地懂得了，以前人们寻求美德的教师时首先在寻求着什么。
人们在寻求安睡与促进安睡的罂粟花！

查拉图斯特拉在讲坛前听智者讲论睡眠的美德。他感到很无聊，于是观察一同听讲的少年们。

他发现少年们的衣着非常奇特。具体地说，少年们的衣着有 $60$ 种特点，第 $i$ 种特点的特征值为 $2^{i-1}$ 。

他每次会观察两个少年，如果有一种衣着特点只出现在一个少年身上，而不在另一个少年身上，查拉图斯特拉就会强迫症发作，并得到等同于该特点特征值的厌恶度。

他想要把少年们站成若干组，使得在每组中，不管他选哪两个少年，都会得到 $<x$ 点厌恶度。查拉图斯特拉称这样的组是好的。

他有时也会使一个少年自成一组，此时不管怎样这个组都是好的。

他想要知道，这样满足条件的组最多可以包含几个少年呢？

有时少年也会回家换衣服，回来时衣着特点会有所改变。

输入格式

输入数据第一行包括三个整数 $n,q,x$，表示少年的人数，少年回家换衣服的次数和阈值。

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$，$a_i$ 表示初始时第 $i$ 个少年衣着特点的特征值之和。

接下来 $q$ 行，每行两个整数 $ind,val$，表示编号为 $ind$ 的少年刚回家换衣服回来，衣着特点的特征值之和改为 $val$ 。

输出格式

输出 $q+1$ 行，每行一个非负整数。

第 $i$ 行的数表示第 $i$ 次修改之前的答案。

第 $q+1$ 行的数表示全部修改完以后的答案。

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

提示

对于 $20\%$ 的数据，满足 $n\le 20$。

对于 $30\%$ 的数据，满足 $n\le 1000$。

对于 $50\%$ 的数据，满足 $n\le 50000$。

对于另外 $20\%$ 的数据，满足 $x$ 是 $2$ 的整次幂。

对于$80\%$的数据，满足$q=0$。

对于 $100\%$ 的数据，满足 $1\le ind\le n\le 100000,0\le q\le 100000,0\le x,a_i,val< 2^{60}$。