Time limit: 1 seconds

Memory limit: 256 megabytes

It wasn't only wickedness and scheming that made people unhappy, it was confusion and misunderstanding.—Atonement, Writer, Ian McEwan

题目描述

“本以为抓个小贼，没想到捅了老窝”

昊京在小贼的带领下进入了小贼的老窝，老窝的形状是一个包含$n$个节点的满二叉树。二叉树以$1$为根节点，对于编号为$x$的非叶子节点，都有两个儿子，左儿子编号为$2x$，右儿子编号为$2x+1$。初始时$n$个节点上都没有小贼。

现在有$q$次行动，每次行动分为3类：

$1 \ x$: 昊京站在节点x，询问每个小贼与昊京的距离之和

$2 \ x$: 节点x出现小贼

$3 \ x$: 节点x上的小贼消失

对于每次操作1，你都需要输出对应的答案。

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

输入

第$1$行输入两个正整数$n, q$

第$2$行到第$q+1$行，每行输入两个数$type, x$。其中$type$为行动的类别，$x$为目标节点。

输出

对于每个$type=1$的询问，需要输出对应的答案，答案之间以空行分隔。

限制

$n, q <= 131071, type \in \{1,2,3\}$，保证 $n=2^h-1$，其中h为正整数；

保证对于每个2操作，目标节点$x$原本没有小贼；

保证对于每个3操作，目标节点$x$原本有小贼。

7 6
1 3
2 4
2 7
1 3
3 4
1 3

0
4
1

样例解释

对于第一次询问，老窝中并没有小贼，距离之和为0；

对于第二次询问，节点4和节点7中有小贼，距离之和为3+1=4；

对于第三次询问，节点7中有小贼，距离之和为1。

Postscript

For someone special: Is not general incivility the very essence of love?