3728. 示范班

单点时限: 2.0 sec

内存限制: 256 MB

“下面我临时组成了示范班,为大家示范齐步走”
“全体立正”
“报数”
“一”,“二”,“三”,“四”,“五”,”七“——

正在列队的同学们,忍俊不禁。

于是, Cuber QQ 被委托为教官们提升数学能力。

Cuber QQ 觉得他辅导基础数学无法体现他的能力,所以他辅导教官们学习位运算。

位运算中有三种最基础的位运算:

  • 按位与 and : 相同位的两个数字都为 $1$ ,则为 $1$ ;若有一个不为 $1$ ,则为 $0$ ;

  • 按位或 or : 相同位只要一个为 $1$ 即为 $1$ ;

  • 按位异或 xor : 相同位不同则为 $1$ ,相同则为 $0$ 。

为了考察教学成果, Cuber QQ 决定和教官们玩一个游戏。

教官们需要维护一个初始为空集的正整数集合 $S$ (不允许有重复的元素), Cuber QQ 会给出一些操作,操作一定是以下两种中的其中一个:

  • add x ,插入给定的 $x$ , 若集合中已有 $x$ 存在 , 则不进行任何操作;
  • query ,查询 $a_i\; and\; a_j\; and\; a_k$ 的最大值, 其中 $a_i,a_j,a_k\in S, a_i \not= a_j, a_i \not= a_k, a_j \not= a_k$

教官们需要针对每一个 query 给出答案。

输入格式

第一行给出正整数 $n$ ( $1\le n\le 10^6$ ), 表示操作的次数。

接下来 $n$ 行, 每行给出第 $i$ 次操作,操作的输入格式一定是以下两个中的其中一种:

  • add y
  • query

输入采用强制在线,每一个操作的 $x=y \; xor\; LastAns$ ( $1\le x_i\le 10^6$ ) ,其中 $LastAns$ 为上一次查询的答案, 初始 $LastAns=0$ 。

数据保证对于所有 query 发生的时候, 集合大小至少为 $3$ 。

输出格式

对每一个查询, 输出一行一个整数,表示答案。

样例

Input
4
add 1
add 2
add 3
query
Output
0
Input
10
add 1
add 2
add 3
query
add 7
query
add 5
query
add 9
query
Output
0
2
2
3

14 人解决,26 人已尝试。

18 份提交通过,共有 70 份提交。

6.1 EMB 奖励。

创建: 5 年,2 月前.

修改: 5 年,2 月前.

最后提交: 3 年,8 月前.

来源: EOJ Monthly 2019.9

题目标签