B. 任何邪恶? 终将绳之以法!

    Type: Default 1000ms 256MiB

任何邪恶? 终将绳之以法!

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

题目描述

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

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

现在有qq次行动,每次行动分为3类:

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

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

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

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

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

输入

11行输入两个正整数n,qn, q

22行到第q+1q+1行,每行输入两个数type,xtype, x。其中typetype为行动的类别,xx为目标节点。

输出

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

限制

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

保证对于每个2操作,目标节点xx原本没有小贼;

保证对于每个3操作,目标节点xx原本有小贼。

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?