ALLIN1 - All in One


Before you begin, you should try this problem! AVL Tree

This problem is simple. Initially, there is a list and it's empty. Then you are given four types of query.

  1. Insert data to the list
  2. Remove data from the list
  3. Print an index (1-based) from a specified data after the list was sorted ascendingly
  4. Print data from a specified index (1-based) after the list was sorted ascendingly

Input

Input contains several lines. Each line follows one of these formats.
1 n: Insert n (0 ≤ n ≤ 231 - 1) to the list
2 n: Remove n from the list. If n was not found, do nothing
3 n: Print n's index (1-based) after the list was sorted ascendingly
4 i: Print data on i-th index (1-based) after the list was sorted ascendingly (0 ≤ i ≤ 231 - 1)
-1: End of input

Output

For each query 3, print n's index in one line. If n was not found, just print -1
For each query 4, print data on i-th index in one line. If the index is not valid, just print -1

Example

Input:
3 20
-1 Output: -1 

hide comments
Min_25: 2017-04-24 10:20:07

The maximum number of queries is around 3000000.

pvsmpraveen: 2017-04-23 14:05:02

There should be an upper limit mentioned on how many values at max will be in present in the list ,
clearly even if all operations are O(1) we cannot run loop 2^31 to even scan them , there much be a mention. Maybe that will help. Thank you

Re: I didn't mention it because it's part of the challenge. Time limit was set carefully to only accept well-designed solution.

Last edit: 2017-04-23 16:38:04
pvsmpraveen: 2017-04-23 05:51:30

4 i: Print data on ith index (0 <= i <= 2^31 - 1)
type 4 : Print data from a specified index (1-based) after the list is sorted ascendingly

These two contradict each other! is it 0 based or 1-based?

Re: Sorry for the ambiguous description. All problem description apply to both input and output format. So, yes, all index are 1-based.

Last edit: 2017-04-23 06:46:15
Vipul Srivastava: 2017-04-22 18:55:02

how many lines can be there? And will there be unique numbers always in the list?

Re: (1) Assume infinite (actually it's not); (2) Yes.

Last edit: 2017-05-16 17:12:03

Added by:Lucas
Date:2017-04-22
Time limit:1s-1.350s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All