暂无测试数据。

作为被异世界召唤的勇者，你的任务就是打败大魔王。为了铸就能够打败大魔王的最强之剑，你收集了 $n$ 种原材料。所有原材料从 $1$ 到 $n$ 依次编号，编号为 $i$ 的原材料有一个特征值 $a_i$ 和强度 $b_i$。

用 $S$ 表示一个原材料的集合，定义 $xor(S)$ 为 $S$ 中所有原材料的特征值做异或运算的结果，$sum(S)$ 则表示 $S$ 中所有原材料的强度之和。

一个原材料集合 $S$ 能够铸就一把剑，当且仅当它不存在一个子集 $S'$ 使得 $xor(S')=0$，而用 $S$ 中的原材料铸就的剑，强度为 $sum(S)$。

现在有 $q$ 次询问或修改，询问就是给出一段区间 $[l,r]$，询问在编号为 $l,l+1,...,r-1,r$ 的原材料中选出一个子集，能铸造的剑的最大强度是多少（只询问，不改变序列信息）；修改就是修改某种原材料的特征值和强度。

输入格式

第一行，一个正整数 $n$

接下来 $n$ 行，每行两个数字，第 $i$ 行的两个数字依次为 $a_i$、$b_i$

接下来一行，一个正整数 $q$

接下来 $q$ 行，每行的第一个数字是 $type$，如果 $type=0$ 表示一次查询，接下来给出两个数字，分别对应 $l,r$，表示一次在区间 $[l,r]$ 上的查询。如果 $type=1$ 表示一次修改，接下来给出三个数字，分别对应 $x,a,b$，表示把编号为 $x$ 的原材料的特征值修改为 $a$，强度修改为 $b$。

输出格式

对每个询问输出一行，表示用查询区间中的原材料所能铸就最强之剑的强度。

数据范围

对于前 $20\%$ 的数据，$n,q \leq 5$

对于前 $40\%$ 的数据，$n\leq 20$，没有修改操作

对于前 $60\%$ 的数据，$n,q \leq 1000$

对于 $100\%$ 的数据，$n\leq 10^5, q \leq 10^4$，$1\leq a_i,b_i \leq 10^9$

对于后 $60\%$ 的数据，修改与查询的出现概率都是 $\frac{1}{2}$

5
1 2
2 1
3 2
4 1
5 2
5
0 1 5
0 2 4
0 3 5
1 5 5 10
0 1 5

6
4
5
14