题目描述
小火车觉得对生活已经没有什么好留恋的了,于是决定前往二次元去寻找真爱。
但是跨越次元是不被神所允许的,小火车决定和神进行比赛,神给了他一个题,你能帮忙解出来吗?
从前有三堆集合分别是 {Ai},{Bi},{Ci} 我们认为 Bi=(j∈Ai∩Bj)∪Ci 而 Ai 里的元素一定小于 i 任意时刻两个不同的 C 集合的交集为空,现在神告诉你 A 集合以及 C 集合的大小,你能告诉他对于我的询问集合 S,∣i∈S∪Bi∣ 是多少么。
实际上你要支持的操作如下:
- 给定集合 A,令 n 加一,多了个新的 An 和 Bn,Cn 的大小为 k;
- 把 Ci 的大小改成为 k;
- 询问集合 S;
输入格式
第一行一个正整数 m 表示操作总数,接下来 m 行每行一个操作。
如果是 1 号操作,格式为 Add t 后跟 t 个整数,t 表示 An 的大小,t 个整数表示集合 An。
如果是 2 号操作,格式为 Update i k;
如果是 3 号操作,格式为 Query t 后跟 t 个整数,含义同上。
数据保证合法。为了体现程序的在线性 1 号操作集合里的元素都需要异或上上次的答案,初值为 0(注意 t 不需要)。
输出格式
对于每个 3 号操作输出一行一个整数表示答案。
样例
4
Add 0 1
Query 1 1
Update 1 4
Query 1 1
1
4
数据范围与提示
用 n 表示插入数量,用 q 表示询问数量。
对于 20% 的数据,满足 n,q≤50,Update 操作数量为 0,A 集合和询问集合总大小 ≤700;
对于 40% 的数据,满足 n,q≤1000,Update 操作数量为 0,A 集合和询问集合总大小 ≤20000;
对于 100% 的数据,满足 n≤200000,q≤100000,Update 操作数量 ≤100000,A 集合和询问集合总大小 ≤600000;k≤1000。