You are building firmware for a seismograph's onboard logger. Signed amplitude readings arrive one at a time and are permanently appended to the instrument's register (nothing is ever removed, and a reading can repeat). Periodically the analysis software issues a query: given a target value, is there a way to pick two distinct logged entries (two separate readings taken at possibly the same or different times) whose amplitudes add up exactly to that target? Note that if a value has only been logged once so far, it cannot be paired with itself — a second, independent logging of that same value is required to use it twice in a sum.

Process a sequence of operations in order. Each operation is either LOG v (append reading v to the register) or QUERY x (ask whether two distinct entries currently in the register sum to x).

Input format

• Line 1: a single integer n, the number of operations.
• The next n lines each contain either LOG v or QUERY x.

Output format

For every QUERY operation, in the order encountered, print 1 if some two distinct logged entries sum exactly to the queried value, otherwise print 0. Print one result per line; do not print anything for LOG operations.

Constraints

• 1 <= n <= 20000
• -100000 <= v <= 100000 for every LOG
• -200000 <= x <= 200000 for every QUERY
• There is at least one operation.

5
LOG 1
LOG 3
LOG 5
QUERY 4
QUERY 7

1
0

4
LOG 2
QUERY 4
LOG 2
QUERY 4

0
1