Vivek and Siddhartha are die-hard cricket fans. They recently watched the IPL 2022 Auction and decided to conduct a Mock Auction for fun and in a different way.
Vivek has an empty bag and a large number of white balls on which nothing is written. Siddhartha will tell Vivek to do Q operations, each of which is of one of the following three types:-
Type 1: Write an integer Xi on a blank ball and put it in the bag.
Type 2: For each ball in the bag, replace the integer written on it with that integer plus Xi.
Type 3: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.
For each 1 ≤ i ≤ Q, you are given the type Pi of the i-th operation and the value of Xi if the operation is of Type 1 or 2.
Print the integers recorded in the operations of Type 3 in order. These printed integers would be the price at which the players are bought.
Constraints
1 ≤ Q ≤ 2×10^5
1 ≤ Pi ≤ 3
1 ≤ Xi ≤ 10^9
All values in input are integers.There is one or more i such that Pi=3.
If Pi=3, the bag contains at least one ball just before the i-th operation.
Input
Input is given from Standard Input in the following format:
Q
query1
query2
:
queryQ
Each ith query in the 2-nd through (Q+1)-th lines is in the following format:
1 Xi
2 Xi
3
The first number in each line is 1 ≤ Pi ≤ 3, representing the type of the operation. If Pi=1 or Pi=2, it is followed by a space, and then by Xi.
Output
For each operation with Pi=3 among the Q operations, print the recorded integer.
VIvek will do the following operations:-
Therefore, we should print 3 and 7, in the order they are recorded.