BICYCLE

The Mayor decided to build a bicycle parking lot at a location along the river. Due to strong winds, cyclists moving to the right may find it more (or less) difficult than cyclists moving to the left to reach the parking lot. Specifically, for given integers ~a~, ~b~, depending solely on the wind conditions, the difficulty for each cyclist to the left of the parking lot is their distance from the parking lot multiplied by the constant ~a~, while the difficulty for each cyclist to the right of the parking lot is their distance from the parking lot multiplied by the constant ~b~. The Mayor wants to place the parking lot in a way that minimizes the total difficulty, which is the sum of the individual difficulties of all cyclists.

Since the Mayor doesn't know exactly the positions of the cyclists or the wind conditions, he tries various scenarios for placement. There are Q queries, of three different types:

1 x: Introducing a new cyclist at position x along the river, where x is a positive integer.

2 x: Removing a cyclist from position x along the river. Note that before removal, there will be at least one cyclist at position x.

3 a b: Calculating the minimum possible total difficulty if the parking lot is placed at the best possible position, given that the wind constants are the integers a and b.

Write a program that reads this data and for each query of type 3 finds the minimum total difficulty. Assume that there can be more than one cyclist at each position.

Input

The first line of input will contain an integer Q: the total number of queries to follow. Each of the next Q lines corresponds to a query. Each line may have one of the forms "1 x", "2 x", or "3 a b", where x, a, b are positive integers.

Output

The output should consist of as many lines as there are type 3 queries in the input, and each of these lines should contain a single integer: the answer to the corresponding type 3 query.

Constraints

1 ~\le~ Q ~\le~ 300.000
1 ~\le~ x ~\le~ 1.000.000.000
1 ~\le~ a, b ~\le~ 1.000
Execution time limit: 1 sec.
Memory limit: 64 MB.

Note: In at least 70% of the input examples, it will hold that x ~\le~ 100.000.

Example of Input - Output:

STDIN (bicycle.in)

8
1 1
1 2
1 3
3 1 1
2 2
1 4
1 5
3 3 1

STDOUT (bicycle.out)

2
9

Explanation of the Example: In the first case, the parking lot will be placed at position 2, while in the second case, it can be placed either at position 1 or at position 3.