Chika has been given a data structures problem and is trying to use a rage tree to solve it. Can you help her? The problem statement is:

Given an initially empty multiset of integers, support the following operations:
1. INSERT(t) - Insert t into the multiset
2. COUNT(t) - Count how many integers in the multiset are less than or equal to t
3. SUM(t) - Compute the sum of all integers in the multiset less than or equal to t

Constraints

~1 \le Q \le 10^6~

~1 \le t_i \le 10^6~

Input Specification

The first line contains one positive integer, ~Q~.

The next ~Q~ lines each contain two integers. The first is between 1 and 3 inclusive, indicating the operation as per above. The second is the value of ~t_i~, the value of ~t~ for the ~i~th operation.

Output Specification

For each COUNT and SUM operation - output the computed value. The values should be printed one per line in the order they were presented in.

Sample Input

3
2 1000000
1 17
3 18

Sample Output

0
17