[Ynoi2014]在太阳西斜的这个世界里

题目背景

![](https://cdn.luogu.com.cn/upload/pic/45500.png) 现在我的梦想实现了 也留下了美好的回忆 可以说没有任何遗憾了吧 ![](https://cdn.luogu.com.cn/upload/pic/45511.png) 今天真是多谢你了 让我体验了许多美好 这全都是托你的福 我留下了如同美梦一般的回忆 不过时间到了 最后我还想拜托你一件事 ![](https://cdn.luogu.com.cn/upload/pic/45522.png) 希望你可以把我忘掉

题目描述

珂朵莉需要维护一棵初始为空的红黑树,进行 $n$ 次操作。 对于重复的整数,我们认为插入时间晚的一个更小。 操作有两类: * $op=1$:在红黑树上插入一个整数$x$。 * $op=2$:给出 $x$,询问从 $1$ 到 $x$ 的整数中等概率选取一个插入到红黑树上,造成的旋转次数的期望值,方便起见,你只要输出 期望值$\times x$,(可以证明这是一个整数)。

输入输出格式

输入格式


第一行一个整数 $n$。 接下来 $n$ 行,每行两个由空格分隔的整数 $op,x$,表示一次操作。

输出格式


对每个 $op=2$ 的操作,输出一行,包含一个整数,表示答案。

输入输出样例

输入样例 #1

10
2 5
1 3
1 4
2 3
2 4
2 5
1 4
2 3
2 4
2 5

输出样例 #1

0
0
2
3
0
0
0

说明

红黑树是一棵二叉查找树,每个点有颜色(红/黑)。 每次执行插入操作时,新插入的点为红色,操作方式和普通二叉查找树相同。 如果出现两个红色的点互为父子,如图进行调整(操作是左右对称的,对称操作在图中不再重复列出;黑色三角形表示空或以黑色点为根的子树),调整可能需要连续进行多次。 调整完毕后,把根设为黑色。 ![](https://cdn.luogu.com.cn/upload/pic/45533.png) Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078 $1\leq n\leq 2\times 10^5$,$1\leq op\leq 2$,$1\leq x\leq 10^8$。