题目背景

「地牢中回荡着尖叫声...」

打完世花的 ac 进入地牢刷灵气……

花后地牢十分险恶，ac 想在地牢里搭满单向门。

题目描述

ac 世界里的地牢有 $n$ 个小房间，恰好存在 $n-1$ 条过道，并且每个小房间连通。第 $i$ 个小房间生成的怪在一个时刻最多只会存在一个，且伤害为 $a_i$。

为了方便刷灵气，ac 在每个过道上建了一个单向门。

每一秒会发生以下几个事件之一：

1. 第 $x$ 个房间生成了一个怪。怪不会穿墙，只会顺着单向门方向移动。

2. 第 $x$ 个房间生成的怪被 ac 的仆从干掉了。

3. ac 想要挂机刷怪，于是他希望知道，如果从时刻 1 开始站在房间 $x$ 一直到当前时刻，受到伤害最多的一个时刻所受伤害是多少。

这里定义一个时刻受到伤害为可以走到 ac 所在房间的怪的伤害值总和，“可以走到”定义为可以穿过若干条单向门到达 ac 的房间（若干可以为 $0$）。ac 非常强大，不会中途被怪打死。

当然，ac 所在的位置不会改变怪的刷新和仆从的行为。

简化版题面

一棵树，每个点有个点权，每条边有个方向。

有个集合，一开始为空，三个操作：

1. 在集合中加入一个点。
2. 删除集合中的一个点。
3. 给出一个点 $x$，询问集合中满足可以走到 $x$ 的点的点权之和的历史最大值。

输入格式

第一行，两个整数 $n,m$，分别表示房间个数和事件个数。

接下来一行，共 $n$ 个整数，第 $i$ 个数表示 $i$ 房间中怪的伤害 $a_i$。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 与 $y$ 有一条过道，单向门方向为 $x\rightarrow y$ 。

接下来 $m$ 行，第 $i$ 行两个整数 $fl,x$，表示第 $x$ 号房间发生了 $fl$ 号事件。

对于 $fl=1$ 的操作，保证 $x$ 号房间没有怪。

对于 $fl=2$ 的操作，保证 $x$ 号房间有怪。

输出格式

对每一个 $fl=3$ 的事件，输出一个整数表示答案，并用换行隔开。

5 7
1 2 3 4 5
1 2
3 1
4 3
3 5
1 4
3 1
2 4
1 3
1 5
3 1
3 5

4
4
8

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

0
12
8

提示

样例一说明

第一个询问中，时刻 $1$ 存在怪的房间为 $\{4\}$，$4$ 号房间的怪可以走到 $1$ 号房间，因此答案为 $a_4=4$。

第二个询问中，受到伤害最大的时刻为时刻 $1$，答案为 $a_4=4$。其中时刻 $5$ 存在怪的房间为 $\{3,5\}$，而 $5$ 号房间的怪走不到 $1$ 号房间，因此此时刻受到伤害为 $a_3=3<4$，不是最大值。

第三个询问中，受到伤害最大的时刻为时刻 $5$，$3,5$ 号房间的怪均可走到 $5$，因此答案为 $a_3+a_5=8$。

---

数据范围

「本题采用捆绑测试」

对于 $10\%$ 的数据，$n,m \leq 2000$。

对于另 $10\%$ 的数据，过道 $(x,y)$ 单向门满足 $x<y$。

对于另 $30\%$ 的数据，不存在 2 事件。

对于 $100\%$ 的数据，$1\leq n,m \leq 2\times 10^5$，$1\leq a_i\leq10^4$。

但是地牢幽魂就是穿墙怪（）（）（）

不会真的有人会在地牢里搭满单向门吧。