AIR Triplet

题号：NC235473
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

翼人的诅咒早就在第一千个夏天被打破了，所以化作名为 Air 的乌鸦的往人就不需要再想这个问题了，开始致力于解决困扰人们多年的 3-SUM 问题。但是 3-SUM 问题很困难，所以他希望能解决 3-AIR 问题。

小 L 定义对于三元组 $(i,j,k)$ ，如果其满足 $1\le i<j<k\le n$ 且 $a_i\oplus a_j=0,a_j\oplus a_k=0$ （其中 $\oplus$ 为按位异或），那么我们称其为 3-AIR 三元组。你除了要求出有多少 3-AIR 三元组，还需要面临一些单点修改。

具体而言，您面临的问题是：现在有一个长 $n$ 的序列 $a$ ，有 $m$ 次操作，每次操作给定 $x,y$ ，你需要将 $a_x$ 修改为 $y$ ，然后对于每次修改输出修改完的数列中，有多少对 $(i,j,k)$ 满足 $1\le i<j<k\le n$ 且 $a_i\oplus a_j=0,a_j\oplus a_k=0$ ，其中 $\oplus$ 为按位异或。

输入描述:

第一行两个正整数 。

接下来一行  个正整数，代表序列 。

后面  行每行两个正整数代表 。

输出描述:

 行，每行代表一次修改后的答案。

示例1

输入

复制

输出

复制

1
4

备注:

 的数据，满足 。