In the (fixed) project template from task A00, implement a data structure that supports faster insertions and queries than std::unordered_set even with no foreknowledge, besides the input type (32-bit non-negative integers.

This version should be used when "-t 6" command line is present.

Input

Sequence of non-negative integers for queries or insertions, with "-1" switching between insert and query modes.

Output

Query results. 1 if the queried integer is present in the set or 0 if it is not.

Constraints

• Queries and insertions are in the range [0..2^31 - 1].
• The number of queries will be less than 10^8.

Example

Input:

2 4 6 8 10 -1 3 4 5 6 7

Output:

0
1
0
1
0