测试数据来自 system/1620

背景

Crash觉得小白逛公园有点简单了，稍微加强了一下……

描述

小新经常陪小白去公园玩，也就是所谓的遛狗啦……在小新家附近有n个公园，这些公园通过一些路径相连，并保证每两个公园之间有且仅有一条通路相连（也就是说这是一棵树），小白早就看花了眼，自己也不清楚该去哪些公园玩了。
小白对每个公园都有一个评价（可正可负），并且它只会让小新做两件事：
1. 询问公园a到公园b路径上最大连续公园的评价和，就是说我们把公园a到公园b路径上的公园（包括a和b）排成一条直线，那么小白希望知道一段连续的公园的评价和最大为多少。

2. 修改公园a到公园b路径上（包括a和b）每个公园的评价值。

小新现在已经处理不了n超过10的情况，因此请你来帮忙……

格式

输入格式

第一行有一个自然数，表示n
第二行有n个自然数，表示一开始小白对每个公园的评价（评价值的绝对值不超过10000）
下面有n-1行，每行两个数a和b，表示公园a和公园b直接由道路相连
再下面一行有一个自然数，表示m
最后m行，每行第一个数k表示要执行的操作。如果k为1，那么后面有两个自然数a和b，表示询问公园a到公园b路径上（包含a和b）最大的连续公园评价和（如果这条路径上每个公园的评价都为负数，那么最大连续和为0）。如果k为2，那么后面有三个自然数a、b和c，表示把公园a到公园b路径上所有的公园（包括a和b）的评价都修改为c。（c的绝对值不超过10000）

输出格式

对于每次询问，输出最大连续和。（用空格隔开，最后要有换行符）

样例1

样例输入1

5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5

样例输出1

5 9

限制

小数据1s，大数据2s
（时间是足够的……）

提示

对于30%的数据：n,m <= 100
对于70%的数据：n,m <= 50000
对于100%的数据：n,m <= 100000