Introduction

平静的小曲

When a shadow falls across your world,
and your enemy wants nothing but your annihilation...
Where will you find allies,
in a desperate struggle for survival?
你也许也意识到了这件事
旅船是未来的虚幻，战车正指引着我们的命运
硬币抛出之后，正逆的转换从未停止
前方是毁灭亦是重生

Background

一群人围着篝火，在严寒中艰难生存。他们彼此的信任正在消散。只剩所谓的“最信任的人”——坐在他们旁边。当一群信任的人聚集在一起，便成为了领导力量。 但这里风云变换，有时信任会改变崩塌，有时一些人的团队地位会扶摇直上，亦或一落千丈。
活在这种痛苦之中，这是他们应得的报应。

Description

给定一个序列 \(x\)， 每两个相邻的元素中间有一条有向边相连。 有以下操作

• 翻转一条边
• 修改一个点的权值
• 查询链（即首尾相接的箭头）最大值
• 查询一个点能到达点的权值总和

Format

Input

第一行一个数 \(n\) 代表序列长度

第二行 \(n\) 个数代表序列 \(a\)

第三行 \(n-1\) 个数，第 \(i\) 个数代表连接 \(x\) 和 \(x+1\) 的边。 1代表从 \(x\) 到 \(x+1\), 0代表从 \(x+1\) 到 \(x\)

第四行一个数 \(q\) 代表操作数

接下来 \(q\) 行四选一：

• 1 \(x\) 反转连接 \(x\) 和 \(x+1\) 的边
• 2 \(x\) \(y\) 将 \(a_x\)的值修改为\(y\)
• 3 查询链最大值
• 4 \(x\) 查询点x能到达的点的权值总和（包括 \(x\))

Output

回答查询，一行一个

Sample 1

Input1

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

Output1

4
4

Input2

7
1 4 4 4 2 4 1
1 0 1 0 0 1
12
3
1 3
2 1 3
4 1
3
1 5
1 4
1 3
2 6 1
1 2
4 4
3

Output2

10
7
18
8
19

Input 3

6
4 2 4 1 4 4
1 0 1 0 1
9
1 1
3
4 1
1 4
3
2 4 1
4 2
2 3 2
3

Output 3

10
4
13
6
11

Limitation

对于20%的数据

\( n\le 10^3\)
\( q\le 10^3\)

对于另外各 15% 的数据

没有 \(1,2,3,4\) 操作

对于100% 的数据

\( n \le 10^5\)
\( q \le 10^5\)
\( 1 \le a_i \le 10^9\)