Problem
q 個のクエリと、最初は数値 0 のみを含むマルチセット A があります。クエリには次の 3 種類があります。
- +x —マルチセット A に数値 x を追加します。
- -x —マルチセット A から数値 x を 1 回削除します。この時点で、少なくとも 1 つの数値 x がマルチセットに存在することが保証されます。
- <強い>? x —数値 x が与えられた場合、マルチセット A から数値 x と数値 y の最大ビット単位の排他的 OR (XOR とも呼ばれます) を計算する必要があります。
マルチセット —これは、複数の同一要素を許可するセットです。
入力:
入力の最初の行には、数値 q (1 ≤ q ≤ 200000) — が含まれます。 Vasiliy が処理する必要があるリクエストの数。
入力の次の q 行のそれぞれに、「+」、「-」の 3 つの文字のいずれかが含まれています。また "？"および数 x
i (1 ≤ x
i ≤ 10
9)。入力にクエリ「?」が少なくとも 1 つあることが保証されます。
数値 0 は常にマルチセットに存在することに注意してください。
出力:
「？」のようなすべてのリクエストに対して単一の整数を出力します —数値 x
i とマルチセット A の任意の数値のビット単位の XOR の最大値。
例:
<本体>
| 入力 |
出力 |
10
+8
+9
+11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11 |
11
10
14
13 |