Problem A
Binary Search Tree Operations

Your task is to implement a data structure that handles two operations: insertion of a number and checking if a number exists in the structure.

More specifically, the data structure should support the following two operations:

1. insert(k) - Add a positive integer $k$ to the data structure. If the number already exists in the data structure, it should not be added multiple times.

2. exist(k) - Check if a positive integer $k$ already exists in the data structure. Print 1 if it exists, otherwise 0.

After all operations, the program should print all the numbers in the structure in sorted order.

These operations should be performed efficiently.

Input

The first line of input consists of an integer $N$ $(1 \leq N \leq 5 \cdot 10^5)$, the number of operations of type $1$ or $2$.

The following $N$ lines describe one operation each. There are two types of operations:

• “1 k”, which represents the operation insert(k) $(0 \leq k \leq 10^9)$, as described above.

• “2 k”, which represents the operation exist(k) $(0 \leq k \leq 10^9)$, as described above.

Output

For each operation starting with “2” (exist(k) operation), the program should print 1 if the number $k$ exists in the data structure, and 0 otherwise. Answer each query in the same order as they appear in the input, one per line.

After all operations, the program should also print all the numbers in the data structure on a new line, sorted in ascending order, separated by spaces.

Scoring

Your solution will be tested on a set of test case groups. To receive points for a group, you must pass all test cases in the group.

Explanation of Sample 1

After the first operation insert(5), the data structure contains the number 5.

After insert(10), the data structure contains the numbers 5 and 10.

exist(5) returns 1 because the number 5 exists in the data structure.

exist(7) returns 0 because the number 7 does not exist in the data structure.

insert(7) adds the number 7.

exist(7) returns 1 because the number 7 now exists in the data structure.

6
1 5
1 10
2 5
2 7
1 7
2 7

1
0
1
5 7 10

5
2 10
1 10
2 10
1 10
2 10

0
1
1
10