← 返回题目列表

Codeforces · 817/E

E. 选择指挥官

中文机器翻译题面 查看原题

你可能还记得上一轮,Vova 目前正在玩一款名为《帝国之怒》的战略游戏。

沃瓦设法建立了一支庞大的军队,但却忘记了军队的主要人物——指挥官。所以他尝试聘请一名指挥官,他想选择一个会受到战士尊重的人。

每个战士都由他的个性代表 - 一个整数 pi。每个指挥官都有两个特征——他的个性pj和领导力lj(都是整数)。仅当 $$p_i \oplus p_j < l_j$$ 时,战士 i 才会尊重指挥官 j($$x \oplus y$$ 是 x 和 y 的按位异或)。

最初Vova的军队是空的。军队可能发生三种不同类型的事件:

- 1 pi — 一名具有 pi 个性的战士加入 Vova 的军队;
- 2 pi — 一名具有 pi 个性的战士离开了 Vova 的军队;
- 3 pi li — Vova 尝试聘请一位具有 pi 性格和 li 领导力的指挥官。

对于第三类事件,Vova 想要知道有多少战士(仅计算那些加入军队但尚未离开的人)尊重他试图雇用的指挥官。

输入

第一行包含一个整数 q (1 ≤ q ≤ 100000) — 事件数。

接下来是 q 行。每一行描述了该事件:

- 1 pi (1 ≤ pi ≤ 108) — 一名具有 pi 个性的战士加入了 Vova 的军队;
- 2 pi (1 ≤ pi ≤ 108) — 一名具有 pi 人格的战士离开 Vova 的军队(保证此时 Vova 的军队中至少有一名这样的战士);
- 3 pi li (1 ≤ pi, li ≤ 108) — Vova 试图雇佣一位性格为 pi 且领导力为 li 的指挥官。至少有一次此类事件。

输出

对于第三种类型的每个事件,打印一个整数 - 尊重指挥官 Vova 试图在该事件中雇佣的战士数量。

示例

输入 #1

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

输出 #1

1
0

注意

在该示例中,在前两个事件之后,军队由性格为 3 和 4 的两名战士组成。然后 Vova 尝试雇用一位性格为 6、领导力为 3 的指挥官,只有一名战士尊重他($$4 \oplus 6 = 2$$,且 2 < 3,但 $$3 \oplus 6 = 5$$,且 5 ≥ 3)。然后性格为 4 的战士离开,当 Vova 试图再次雇用该指挥官时,没有战士尊重他。