BLUNIQ - Unique Code

In Lapak City, every tourist is given a unique code based on their favorite number. If their favorite number is already used as a unique code, that tourist will be given the smallest unused unique code that is larger than his favorite number. For example, a tourist with 42 as his favorite number visits Lapak City. However, unique code 42 is already used. So that tourist is given the unique code 43. If 43 is also used, then that tourist is given the unique code 44, etc.

Every tourist that leaves Lapak City will delete their unique code, that means their code can be used for other newcomer if needed. Continuing the previous example, if the tourist with unique code 43 left Lapak City, and a tourist with favorite number 43 enters, that new tourist will be given the unique code 43.

Initially, all code is unused and no tourist is in Lapak City. On one day, there are N tourist event on Lapak City. Help Lapak City to determine unique code for the tourist.

Input

First line of input is N, the number of event (1 < N < 100000). Next N lines contain the events. For every tourist that visits Lapak City, the input is "1 x", with x is the favorite number of that tourist (1 < x < 1 000 000 000). For every tourist that leaves Lapak City, the input is "2 x", with x is the unique code of that tourist.

Output

For each visiting tourist, output their unique code.

Example

Input:
5
1 42
1 42
1 43
2 43
1 42

Output:
42
43
44
43

Added by:Andy
Date:2016-07-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:BL Scholarship 2016

hide comments
2022-06-08 04:16:23
ordered set saved the day
2019-12-23 20:48:41
cakewalk Thanks @luka_dzimba911
2019-09-15 06:45:45
Segment tree with nodes allocated on the fly.

Hint:
log2(1 000 000 000) == ~30

Max height of the tree is about 30. For every value need to create max 30 nodes. Create nodes while traverse and all will be fine

Last edit: 2019-09-15 06:51:44
2019-03-17 18:14:56
getting TLE for n(logn)^2 :(

Last edit: 2019-03-17 18:15:32
2018-05-18 01:28:20
important x maybe set to <= 10e9 but the output can be greater than 10e9 because if all tourist have favorite number 10e9 output will be greater than limit for x , gave me 2 WA
2017-04-24 14:21:14
How to solve in less memory like other ??
So Curious :|
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.