Chtholly needs to maintain a Red-Black Tree, initially empty, and perform $n$ operations.

For duplicate integers, we consider the one inserted later to be smaller.

There are two types of operations:

• $op=1$: Insert an integer $x$ into the Red-Black Tree.
• $op=2$: Given $x$, calculate the expected number of rotations caused by inserting an integer chosen uniformly at random from the range $[1, x]$ into the Red-Black Tree. For convenience, output the expected value multiplied by $x$ (it can be proven that this is an integer).

Input

The first line contains an integer $n$.

The next $n$ lines each contain two space-separated integers $op, x$, representing an operation.

Output

For each operation with $op=2$, output a single line containing an integer representing the answer.

Examples

Input 1

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

Output 1

0
0
2
3
0
0
0

Subtasks

A Red-Black Tree is a binary search tree where each node has a color (red or black).

Every time an insertion operation is performed, the newly inserted node is red, and the operation is performed in the same way as in a standard binary search tree.

If two red nodes are parent and child, perform adjustments as shown in the figure (the operations are symmetric; symmetric operations are not repeated in the figure; black triangles represent empty nodes or subtrees rooted at a black node). Adjustments may need to be performed multiple times consecutively.

After all adjustments are complete, set the root to black.

$1\leq n\leq 2\times 10^5$, $1\leq op\leq 2$, $1\leq x\leq 10^8$.