小苯有一个神奇的背包，只需要满足一些物品体积的异或和 （） 值不为 ，神奇的背包即可装下这些所有物品，背包此时所装物品的总价值为所有物品的价值之和（加法和）。

现在小苯面前有  个物品，第 个物品的体积为 ，价值为 。小苯会进行 次修改、查询，每次操作都是以下三种之一：

修改：
     将第 个物品的体积修改为 。
     将第 个物品的价值修改为 。

（注意：修改操作是持久生效的，即修改后物品的属性会永久改变。）
查询：
     表示查询：从子数组 中任选物品装入“神奇背包”时，所装物品的的最大总价值。

（特别的，神奇背包没有装入任何物品时，其价值视为 0。）

小苯希望你帮他回答每一次查询，请你帮帮他吧。

输入描述:

本题含有多组测试数据。
第一行一个正整数 ，表示测试数据的组数。
接下来对于每组测试数据，输入包含  行：
第一行两个正整数 ，表示小苯面前的物品个数，以及小苯的操作次数。
接下来  行，每行两个正整数 ，分别表示每个物品的体积、价值。
接下来  行，每行三个正整数，其中第一个是 。
 如果 ，则接下来输入两个正整数是 ，表示将第  个物品的体积修改为 。
 如果 ，则接下来输入两个正整数是 ，表示将第  个物品的价值修改为 。
 如果 ，则接下来输入两个正整数是 ，表示询问从子数组  中选择一些物品装入神奇背包的最大价值。
（数据保证对于每组测试数据，至少存在一次查询操作。）
（保证所有测试数据中， 的总和都分别不超过 。）

输出描述:

对于每组测试数据，输出若干行，每行一个整数，表示对于每次查询操作的回答。

1
4 3
1 3
2 4
3 1
4 2
3 1 3
1 3 4
3 3 4

7
2

样例中，共有四个物品，体积分别为：，价值分别为：。
三次操作：
 首先询问区间  任选物品装入“神奇背包”的最大价值，最优的方案是装入编号  的物品，此时物品体积的异或和  为 ，物品的价值和为 ，最大。
 再将  号物品的体积修改为 。
 此时询问区间  任选物品装入“神奇背包”的最大价值，最优的方案是装入编号  的物品，此时物品体积的异或和  为 ，物品的价值和为 ，最大。