珂朵莉需要维护一棵初始为空的红黑树，进行 $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

子任务

红黑树是一棵二叉查找树，每个点有颜色（红/黑）。

每次执行插入操作时，新插入的点为红色，操作方式和普通二叉查找树相同。

如果出现两个红色的点互为父子，如图进行调整（操作是左右对称的，对称操作在图中不再重复列出；黑色三角形表示空或以黑色点为根的子树），调整可能需要连续进行多次。

调整完毕后，把根设为黑色。

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$。