万寿无疆

题目背景

出题人友善的提示: 你可能是第一次看到这么长的题面，可能对初学的你是一个大挑战，请你认真读题并研究样例。如果还是不理解，那你大可放心自闭，玩玩扫雷之类的或是完成之前的题目

---

8.17就要到了,某不科学的膜法师RyeCatcher很开心,8.17对他而言有什么特殊的含义呢?稻米的新年?然而他并不是位稻米;浪漫的七夕?~~然而他是全队唯一的单身狗~~ 逃);你也许不知道8.17是他某位特别崇敬的人的生日,他决定在今年的817搞一个"大新闻"。

他从蛤学办那里了解到为防今年的庆寿活动被河蟹,上级决定有组织有计划地进行,即\(N\)位膜法师中的每一位膜法师都与一位或多位膜法师存在膜法关系,在某一时刻可能有一位膜法师会成为上司来指挥,这群膜法师通过\(N-1\)条膜法关系构成了一个叫"膜法**树**"的关系网络。组织听说他曾经在OI界摸过鱼,于是奉命他对这次庆寿行动做一些计算

题目描述

他这次要对\(1\)到\(m\)时刻的庆寿行动进行评估计算,评估结果是通过膜力值,每位膜法师都会有的属性来体现。他通过观测者日记得知了在某一时刻某位膜法师上司可能会发布一条"搞一个重要度为\(w_i\)的大新闻"的命令,于是这位上司的膜力值会增加\(w_i\);也有可能发布一个"学习\(s_i\)分钟蛤三篇"的命令,于是这位上司的膜力值都会变成\(s_i\)。

当然,某一时刻大家都在闷声发大财的时候(即不存在发布命令的上司),RyeCatcher就想知道在膜法**树**上第\(x_i\)位膜法师到第\(y_i\)位膜法师的路径上(关系网络保证任意两点之间路径是唯一的)**经过的膜法师中膜力值历史最大值最大是多少**（如果你不明白什么意思可以稍后看样例）

输入输出格式

输入格式

第一行两个正整数\(n\)和\(m\),\(n\)表示膜法师的数量,\(m\)表示要评估的时刻数

第二行n个整数,\(h_i\)表示第\(i\)个膜法师初始的膜力值

第3到第n+1行,每行两个正整数\(u\)和\(v\),表示\(u\),\(v\)之间存在膜法关系

接下来另有m行，代表\(1\)到\(m\)时刻,每行先有一个正整数\(opt\)

若\(opt=1\),则那一行会再输入两个个正整数\(p_i\),\(w_i\)，表示第\(p_i\)个膜法师作为上司发布一条"搞一个重要度为\(w_i\)的大新闻"的命令

若\(opt=2\),则那一行会再输入两个个正整数\(p_i\),\(s_i\)，表示第\(p_i\)个膜法师作为上司发布一条"学习\(s_i\)分钟蛤三篇"的命令

若\(opt=3\),则表示此时大家都在闷声发大财,所以那一行再会给出两个正整数\(x_i\),\(y_i\),表示询问在膜法**树**上第\(x_i\)位膜法师到第\(y_i\)位膜法师的路径上(关系网络保证任意两点之间路径是唯一的)经过的膜法师中,膜力值历史最大值最大是多少

输出格式

对于每个询问(也就是\(opt=3\)),输出一行一个数表示答案

输入输出样例

样例输入#1

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

样例输出#1

4
4

样例解释#1

在第一个时刻第一个膜法师发布了"搞一个重要度为2的大新闻"的命令,因此第一位膜法师的膜力值由2增加为4;

在第二个时刻所有人都在闷声发大财,你需要回答询问,由于第1位膜法师到第2位膜法师的路径上只有那两位膜法师,而且这两人中膜法值的历史最大值就是一号膜法师现在的膜力值4，所以输出答案4;

在第三个时刻,一号膜法师发布了"学习-1分钟蛤三篇"的命令,因此一号膜法师的膜力值变成-1;

第四个时刻所有人都在闷声发大财,因此你需要回答询问，第1位膜法师到第3位膜法师的路径上只有1号与3号膜法师,而且这两人中1号膜法师膜法值曾经最大到达过4(也就是他的历史最大值是4),是这两人中历史最大值最大的,所以输出答案4;

说明

\(1<=n<=20000,1<=m<=100000\),\(-19260817<=h_i<=19260817\)

\(1<=u,v<=n\),\(opt \in [1,3]\)

\(1<=p_i,x_i,y_i<=n\),\(-10000<=w_i<=10000\),\(-19260817<=s_i<=19260817\)

~~由于出题人很懒并没有子任务~~

\(40\%\)数据\(n,m<=1000\),另有\(20\%\)数据保证是一条链,\(100\%\)数据如上所述

输入数据可能很大请使用较快的读入方式

数据很良心