You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 3.0 秒

空间限制： 512 MB

题目背景

曾经，在西西艾弗岛……

题目描述

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

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

因为通往梦魔巢穴的传送门非常不稳定，小 C 可能降落的位置并不确定。具体来说，小 C 会被传送到两只相邻的梦魔之间。每一次进攻时，小 C 可以选择攻击左边或右边离自己最近的梦魔；在击杀一只梦魔之后，与其相邻的梦魔会补上它的位置。

为了确保作战计划万无一失，小 C 想要对于每个位置都求出，如果自己降落在这里，能让他击杀所有梦魔的最小初始攻击力是多少。

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

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

输入格式

从标准输入读入数据。

第一行一个正整数 $n$，代表梦魔的数量。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 只梦魔的防御力。

第三行 $n$ 个正整数 $b_1,b_2,\dots,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$。

注意：每次变动是相互独立的，所有的信息修改都在初始局面中进行。

输出格式

输出到标准输出。

设 $p_i$ 表示小 C 降落在第 $i$ 只梦魔和第 $i+1$ 只梦魔之间时，击杀所有梦魔所需要的最小初始攻击力。

对每次变动输出一行一个整数，表示 $p_1\oplus p_2\oplus \dots \oplus p_{n-1}$ 的值，其中 $\oplus$ 表示按位异或。

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

9
1

样例 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$。

注意第一次变动对第二次变动不产生影响。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务一（$30$ 分）：保证 $n\le 1000$；
• 子任务二（$40$ 分）：保证 $n\le 10^5,q\le 5$；
• 子任务三（$10$ 分）：保证 $1\le a_i,a'_i\le n$；
• 子任务四（$20$ 分）：无特殊限制。

对于所有数据，保证 $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 \times 10^5$。

提示

本题输入量较大，请采用效率较高的读入方式。