梦魇

题目描述

update(2024.12.9) 本题新增一组hack数据，hack数据不计算分数，但是未通过hack数据的提交不会被计入ac题集中。特别感谢 @Andyqian7 提供的hack数据！

曾经，在西西艾弗岛……

有 $n$ 只梦魔会在夜间潜入居民们的梦境世界，让大家整晚做噩梦，无法好好休息。为了西西艾弗岛居民们的幸福，小C 决定潜入梦魔们的巢穴，向它们发起决斗。

在巢穴里，$n$ 只梦魔站成一列，第 $i$ 只梦魔有防御力 $a_i$。如果小 C 的攻击力不严格小于 $a_i$，他就可以击杀这只梦魔。由于战斗经验的增长，击杀梦魔之后小 C 的攻击力将上升 $b_i$。

因为通往梦魔巢穴的传送门非常不稳定，小 C 可能降落的位置并不确定。具体来说，小 C 会被传送到两只相邻的梦魔之间。每一次进攻时，小 C 可以选择攻击左边或右边离自己最近的梦魔；在击杀一只梦魔之后，与其相邻的梦魔会补上它的位置。为了确保作战计划万无一失，小 C 想要对于每个位置都求出，如果自己降落在这里，能让他击杀所有梦魔的最小初始攻击力是多少。

由于梦魔们也在成长，所以它们的防御力和击杀带来的收益可能产生细微的变化。在每次变化之后，小 C 依旧想知道每个位置所需的最小初始攻击力。

但小 C 非常菜，于是他只能拜托你帮他解决这个问题了。

输入格式

第一行一个正整数 $n$，代表梦魔的数量。 第二行 $n$ 个正整数 $a_1, a_2, . . . , a_n$，其中 $a_i$ 表示第 $i$ 只梦魔的防御力。 第三行 $n$ 个正整数 $b_1, b_2, . . . , b_n$，其中 $b_i$ 表示击杀第 $i$ 只梦魔后小 C 攻击力上涨的数值。 第四行一个正整数 $q$，表示梦魔的信息发生了 $q$ 次变动。 接下来依次描述 $q$ 次变动，对于每次变动，输入的第一行包含一个非负整数 $k$，表示在初始局面中有 $k$ 只梦魔的信息发生了变动。接下来 $k$ 行每行三个正整数 $i, a′_i, b′_i$，表示将 $a_i$ 的值修改为 $a′_i$，$b_i$ 的值修改为 $b′_i$。

注意：每次修改都是基于最开始的局面，每次修改均相互独立。

数据范围

对于 $30\%$ 的数据，$n \le 1000$ 对于 $20\%$ 的数据，$n \le 10^5, q \le 5$ 对于 $10\%$ 的数据，$1 \le a_i,a'_i \le n$ 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^6, 0 \le q \le 20, 1 \le a_i,b_i,a'_i,b'_i \le 10^9$ 且保证所有 $q$ 次变动的 $k$ 之和不大于 $5 × 10^5$。

友情提示，本题的输入量非常大，单个测试点大小在50mb左右，因此请采用非常非常快的读入方式。

输出格式

设 $p_i$ 表示小 C 降落在第 $i$ 只梦魔和第 $i + 1$ 只梦魔之间时，击杀所有梦魔所需要的最小初始攻击力。 对每次变动输出一行一个整数，表示 $p1 ⊕ p2 ⊕ · · · ⊕ p_{n−1}$ 的值，其中 $⊕$ 表示按位异或。

样例 #1

样例输入 #1

6
4 9 3 1 7 7
4 2 1 3 1 4
2
2
3 8 1
5 4 3
0

样例输出 #1

9
1

提示

第一次变动后有 $p_1 = 5, p_2 = 8, p_3 = 1, p_4 = 1, p_5 = 4$。 第二次变动后有 $p_1 = 5, p_2 = 3, p_3 = 3, p_4 = 3, p_5 = 7$。