#P18402. Flying Ship Story

Flying Ship Story

Flying Ship Story

Byte Ocean 把众多岛屿分隔开。聪明的人们发明了飞船,从而可以前往其它地方。今天,数百万商人聚集到 Byteland,庆祝一年一度的国际贸易节。你负责维护这里的交易数据库。

最初数据库为空。接下来将发生 qq 个事件,每个事件属于下列两种之一:

  • 1 x y w(1≤x,y,w≤1091\le x,y,w\le10^9):一件新商品开始出售。它来自第 xx 个岛屿,类型编号为 yy,价格为 ww。来自不同岛屿的商品可以具有相同类型。
  • 2 x y(1≤x,y≤1091\le x,y\le10^9):来自第 xx 个岛屿、携带第 yy 类商品的商人,正在寻找来自其它岛屿且属于其它类型的商品。请报告所有符合条件商品中的最高价格。若没有符合条件的商品,报告 0。查询只是搜索,不会从数据库中删除商品。

受 Byteland 技术水平限制,数据库可用的空间很少。你需要在有限空间内高效维护它。

输入格式

第一行包含整数 qq(1≤q≤1 000 0001\le q\le1\,000\,000),表示事件数。

接下来 qq 行,每行描述一个事件,格式如上。但为了强制在线处理,其中的参数经过加密。

令 lastlast 为上一次查询所回答的价格,输入开始时 last=0last=0。对于每个事件,读入的 x,yx,y,以及插入事件中的 ww,其真实值分别为

$$x\oplus last,\qquad y\oplus last,\qquad w\oplus last,$$

其中 ⊕\oplus 表示按位异或。上文给出的参数限制仅对解密后的真实值成立,密文不受这些范围限制。

每次查询完成后,lastlast 变为本次输出的答案,包括答案为 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