問題一覧 > 通常問題

No.2195 AND Set

レベル : / AI推定難易度 : 725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 145
作問者 : Shirotsume / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 8886 / 自分の提出
問題文最終更新日: 2023-01-17 00:28:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 374 (順位表) の他の問題:

Problem Statement

There is an empty set $S$. Process the $Q$ queries described below. The $i$-th query is one of the following $3$ types (exactly $1$ of them).

  • Query 1: Add the integer $x_i$ to the set $S$. If $S$ already contains $x_i$, do nothing.
  • Query 2: Remove the integer $x_i$ from the set $S$. If $S$ does not contain $x_i$, do nothing.
  • Query 3: Print the Bitwise AND of all elements in the set $S$. However, if $S$ is empty, print $-1$.
What is Bitwise AND? (click to expand)

For $2$ non-negative integers $X, Y$, the Bitwise AND of $X$ and $Y$, denoted $X$ $\mathrm{AND}$ $Y$, is defined as follows.

  • When $X$ $\mathrm{AND}$ $Y$ is written in base $2$, the digit in the $2^k$ $(k \geq 0)$ place is $1$ if both the digit in the $2^k$ place of $X$ in base $2$ and the digit in the $2^k$ place of $Y$ in base $2$ are $1$, and $0$ otherwise.

For example, $3$ $\mathrm{AND}$ $5 = 1$. (In base $2$: $011$ $\mathrm{AND}$ $101 = 001$.)

In general, the Bitwise AND of $k$ non-negative integers $p_1, p_2, \dots, p_k$ is defined as $( \dots ((p_1$ $\mathrm{AND}$ $p_2)$ $\mathrm{AND}$ $p_3)$ $\mathrm{AND}$ $\dots)$ $\mathrm{AND}$ $p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, \dots, p_k$.

Constraints

  • All inputs are integers.
  • $1 \leq Q \leq 4 \times 10^5$
  • $0 \leq x_i < 2^{30}$
  • The queries are given in the format described in the problem statement.
  • Query 3 is given at least $1$ time.

Input

The input is given from standard input in the following format.

$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$
Here, each query $query_i$ is given in one of the following formats.

Query 1:

$1$ $x_i$

Query 2:

$2$ $x_i$

Query 3:

$3$

Output

Let $X$ be the number of times Query 3 is given. Print $X$ lines. On the $i$-th line, print the answer to the $i$-th given Query 3.

Sample

Sample 1
Input
7
1 1
1 4
3
2 3
1 1
2 1
3
Output
0
4

When the $1$st query of type $3$ is given, $S = (1, 4)$. Therefore, the Bitwise AND is $0$.

When the $2$nd query of type $3$ is given, $S = (4)$. Therefore, the Bitwise AND is $4$.

Note that even if an add query with the same value is given multiple times, the value is not added multiple times.

Sample 2
Input
20
3  
1 1
2 0
1 3
1 2
1 1
3  
2 0
2 1
2 1
2 1
2 3
2 2
3
1 2
1 2
1 3
2 3
2 1
3
Output
-1
0
-1
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。