【题目描述】

给定一棵$n$个点，以$1$为根的二叉树，每个点要么没有儿子要么有两个儿子，第$i$ 个点有非负点权$a_i$。

现在由深至浅地考虑每个节点$u$，计算其新权值$b_u$：

•若$u$没有儿子，$b_u←a_u$

•若其两个儿子的编号分别为$x, y$，则$b_u←a_u+|b_x−b_y|$。

现在有$q$次询问，每次修改一个点权$a_u$，问修改之后根节点的新权值$b_1$。

【输入格式】

第一行一个正整数$n$，表示树的点数。

接下来$n$行，第$i$行两个非负整数$l_i,r_i$，分别表示点i的左右儿子的编号，若$i$没 有儿子，则$l_i=r_i=0$。

第$n+2$行$n$个非负整数，分别表示$a_1,a_2,··· ,a_n$。

第$n+3$行一个正整数$q$，表示询问数量。

接下来$q$行，每行两个整数$u,x$，表示将节点$u$的权值$a_u$改为$x$。

【输出格式】

对于每个询问，输出一行一个非负整数表示答案。

【样例1输入】

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

【样例1输出】

1  
10  
13 

【样例2】

见题目目录下的$hypnotic2.in$与$hypnotic2.ans$。

该样例满足测试点$2∼3$的限制。

【样例3】

见题目目录下的$hypnotic3.in$与$hypnotic3.ans$。

该样例满足测试点$4∼5$的限制。

【数据范围】

对于所有数据，$1≤n, q≤10^5，a_i≥0$；记$L$为$a_i$在任意时刻的最大值，保证 $L≤20$。

特殊性质A：树的非叶节点构成一条链，且$l_i=i+1,r_i=\frac{n+1}{2}+i$.