4164: Choosing The Commander
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：11
通过：6
题目描述
E. Choosing The Commander
你可能还记得上一轮，沃瓦目前正在玩一款名为“帝国之怒”的战略游戏。
沃瓦设法组建了一支庞大的军队，但忘记了军队中的主要人物——指挥官。因此，他试图聘请一位指挥官，他想选择一位受勇士尊敬的人。
每个战士都由他的个性来表示——一个整数pi。每个指挥官都有两个特点——个性pj和领导力lj（都是整数）。战士i尊重指挥官j，只有当（是x和y的位不包括OR）。
最初，沃瓦的军队是空的。军队可能会发生三种不同类型的事件：
1pi——一名个性为pi的战士加入了沃瓦的军队；
2pi——一个个性为pi的战士离开了沃瓦的军队；
3pili−Vova试图雇佣一名具有人格pi和领导力li的指挥官。
对于每一次第三类事件，沃瓦都想知道有多少勇士（只计算那些加入军队但尚未离开的勇士）尊重他试图雇佣的指挥官。
沃瓦设法组建了一支庞大的军队，但忘记了军队中的主要人物——指挥官。因此，他试图聘请一位指挥官，他想选择一位受勇士尊敬的人。
每个战士都由他的个性来表示——一个整数pi。每个指挥官都有两个特点——个性pj和领导力lj（都是整数）。战士i尊重指挥官j，只有当（是x和y的位不包括OR）。
最初，沃瓦的军队是空的。军队可能会发生三种不同类型的事件：
1pi——一名个性为pi的战士加入了沃瓦的军队；
2pi——一个个性为pi的战士离开了沃瓦的军队；
3pili−Vova试图雇佣一名具有人格pi和领导力li的指挥官。
对于每一次第三类事件，沃瓦都想知道有多少勇士（只计算那些加入军队但尚未离开的勇士）尊重他试图雇佣的指挥官。
As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires.
Vova managed to build a large army, but forgot about the main person in the army - the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.
Each warrior is represented by his personality − an integer number pi. Each commander has two characteristics − his personality pj and leadership lj (both are integer numbers). Warrior i respects commander j only if
(
is the bitwise excluding OR of x and y).
Initially Vova's army is empty. There are three different types of events that can happen with the army:
Vova managed to build a large army, but forgot about the main person in the army - the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.
Each warrior is represented by his personality − an integer number pi. Each commander has two characteristics − his personality pj and leadership lj (both are integer numbers). Warrior i respects commander j only if
( is the bitwise excluding OR of x and y).Initially Vova's army is empty. There are three different types of events that can happen with the army:
- 1pi − one warrior with personality pi joins Vova's army;
- 2pi − one warrior with personality pi leaves Vova's army;
- 3pili − Vova tries to hire a commander with personality pi and leadership li.
Input
The first line contains one integer q (1≤q≤100000) − the number of events.Then q lines follow. Each line describes the event:
- 1pi (1≤pi≤108) − one warrior with personality pi joins Vova's army;
- 2pi (1≤pi≤108) − one warrior with personality pi leaves Vova's army (it is guaranteed that there is at least one such warrior in Vova's army by this moment);
- 3pili (1≤pi,li≤108) − Vova tries to hire a commander with personality pi and leadership li. There is at least one event of this type.
Output
For each event of the third type print one integer − the number of warriors who respect the commander Vova tries to hire in the event.
Example
Input
5 1 3 1 4 3 6 3 2 4 3 6 3
Output
1 0
Note
In the example the army consists of two warriors with personalities 3 and 4 after first two events. Then Vova tries to hire a commander with personality 6 and leadership 3, and only one warrior respects him (
, and 2<3, but 
, and 5≥3). Then warrior with personality 4 leaves, and when Vova tries to hire that commander again, there are no warriors who respect him.输入格式
第一行包含一个整数q（1≤q≤100000）−事件数。
然后是q行。每行描述事件：
1pi（1≤pi≤108）−一名个性为pi的战士加入了沃瓦的军队；
2pi（1≤pi≤108）−一名人格为pi的战士离开了沃瓦的军队（保证此时沃瓦的部队中至少有一名这样的战士）；
3pili（1≤pi，li≤108）−Vova试图雇佣一名具有个性pi和领导力li的指挥官。至少有一个此类事件。
然后是q行。每行描述事件：
1pi（1≤pi≤108）−一名个性为pi的战士加入了沃瓦的军队；
2pi（1≤pi≤108）−一名人格为pi的战士离开了沃瓦的军队（保证此时沃瓦的部队中至少有一名这样的战士）；
3pili（1≤pi，li≤108）−Vova试图雇佣一名具有个性pi和领导力li的指挥官。至少有一个此类事件。
输出格式
对于第三种类型的每一项赛事，打印一个整数——尊重指挥官沃瓦在赛事中试图雇佣的勇士数量。
输入样例 复制
5
1 3
1 4
3 6 3
2 4
3 6 3输出样例 复制
1
0