#P18402. Flying Ship Story
Flying Ship Story
Flying Ship Story
Byte Ocean 把众多岛屿分隔开。聪明的人们发明了飞船,从而可以前往其它地方。今天,数百万商人聚集到 Byteland,庆祝一年一度的国际贸易节。你负责维护这里的交易数据库。
最初数据库为空。接下来将发生 个事件,每个事件属于下列两种之一:
1 x y w():一件新商品开始出售。它来自第 个岛屿,类型编号为 ,价格为 。来自不同岛屿的商品可以具有相同类型。2 x y():来自第 个岛屿、携带第 类商品的商人,正在寻找来自其它岛屿且属于其它类型的商品。请报告所有符合条件商品中的最高价格。若没有符合条件的商品,报告 0。查询只是搜索,不会从数据库中删除商品。
受 Byteland 技术水平限制,数据库可用的空间很少。你需要在有限空间内高效维护它。
输入格式
第一行包含整数 (),表示事件数。
接下来 行,每行描述一个事件,格式如上。但为了强制在线处理,其中的参数经过加密。
令 为上一次查询所回答的价格,输入开始时 。对于每个事件,读入的 ,以及插入事件中的 ,其真实值分别为
$$x\oplus last,\qquad y\oplus last,\qquad w\oplus last,$$其中 表示按位异或。上文给出的参数限制仅对解密后的真实值成立,密文不受这些范围限制。
每次查询完成后, 变为本次输出的答案,包括答案为 0 的情况;插入事件不会产生回答。事件类型编号 1、2 不加密。
输出格式
对于每个查询事件,输出一行一个整数,表示符合条件商品的最高价格;若没有,则输出 0。
若没有查询事件,不输出任何内容。
样例
5
1 2 3 1
1 4 5 2
2 2 2
2 3 7
2 3 4
2
1
0