Description

You need to maintain a multiset that supports three operations:

1. Insert a pair of non-negative integers.
2. Delete a pair of non-negative integers. It is guaranteed that this pair is already in the set.
3. Given a pair of non-negative integers $(x,y)$, ask how many pairs $(a,b)$ in the set satisfy $x\operatorname{xor}a>y\operatorname{xor}b$, where $\operatorname{xor}$ denotes the bitwise XOR operation.

In this problem, all “pairs” refer to ordered pairs.

Input Format

The first line contains a non-negative integer $M$, representing the number of operations.

The next $M$ lines each contain one operation in the following format:

• 1 x y means inserting the pair $(x,y)$.
• 2 x y means deleting the pair $(x,y)$. It is guaranteed that $(x,y)$ appears in the multiset at least once at this moment.
• 3 x y means querying the pair $(x,y)$.

Output Format

Output $M$ lines. For each query, output one line with a non-negative integer, representing the answer to the query.

6
3 1 2
1 3 2
1 4 5
3 6 2
2 3 2
3 6 2

0
1
0

Hint

For the sample, during the first query there are no pairs in the set, so the answer is $0$.

During the second query, the set is $\{(3,2),(4,5)\}$. We have $6\operatorname{xor}3=5>0=2\operatorname{xor}2$, and $6\operatorname{xor}4=2<7=2\operatorname{xor}5$. Therefore, the only pair that satisfies the condition is $(3,2)$, so the answer is $1$.

During the third query, the set is $\{(4,5)\}$. There is no pair that satisfies the condition, so the answer is $0$.

For all testdata:

• $0 \le M \le 2 \times 10^5$.
• $0 \le x, y \le 10^{18}$.

This problem uses bundled tests.

• Idea: FZzzz
• Solution: FZzzz
• Code: FZzzz
• Data: FZzzz

Translated by ChatGPT 5