In the (fixed) project template from task A00, implement a data structure that supports fast batched queries. That is, queries are not interlieved with with insertions, but arrive as a separate batch after insertions.

This version should be used when either the "-t 4" and/or the "-s" command line arguments are 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,147,483,647].
• 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