芙莉莲与英雄的记忆

时间限制：5 秒
内存限制：1024 MB
输入：标准输入
输出：标准输出

题目描述

自从辛美尔、海塔、艾泽和芙莉莲一起打败魔王以来，已经过去了数十年。人类无法像精灵那样长寿，因此随着世代更迭，即使是这样的英雄事迹也逐渐被遗忘。

芙莉莲现在旅途的目的之一，是拜访她过去与英雄团队一起旅行时去过的地点。大陆的地图是一棵树，即任意两个城市之间有且仅有一条路径。沿着树的每条边旅行恰好需要一年时间。

此外，每个城市都有一个值 $s_i$——对当年事件的记忆等级。已知每年所有城市的记忆等级都会减少 $1$。有时会发生以下类型的事件：

• “- $t_i$ $x_i$”：在 $t_i$ 年年初，城市 $x_i$ 中有人建造或修复了辛美尔的纪念碑，或组织了庆祝击败魔王的年度节日。则从该年（含）开始，该城市的记忆停止下降。
• “+ $t_i$ $x_i$”：在 $t_i$ 年年初，城市 $x_i$ 中纪念碑被毁或庆祝活动被取消。则从该年（含）开始，该城市的记忆等级再次每年下降 $1$。

记忆等级不会低于 $0$，也永远不会增加。保证类型 + 的事件仅当之前在同一城市发生过类型 - 的事件且之后没有其他 + 事件时才发生。类似地，类型 - 事件不能跟在同一城市的另一个 - 事件之后。

有时芙莉莲会提出这样的问题：“如果在 $t'_i$ 年年初从城市 $x'_i$ 出发，并且之后城市中不会再有 + 或 - 类型的变化，那么能遇到的击败魔王的英雄的记忆等级最大值是多少？” 请帮助她回答所有她感兴趣的问题。

输入格式

第一行输入两个整数 $n$ 和 $q$——城市数量和询问数量（$1 \le n, q \le 10^5$）。

第二行输入 $n$ 个整数 $s_i$——第 $0$ 年年初城市的初始记忆等级（$0 \le s_i \le 10^9$）。

接下来 $n-1$ 行，每行两个整数 $u_i$ 和 $v_i$，描述树的一条边（$1 \le u_i, v_i \le n$）。保证任意两点之间有且仅有一条路径。

接下来 $q$ 行，每行描述一个询问。每个询问以字符 -、+ 或 ? 开头。前两种情况下，后面跟着两个整数 $t_i$ 和 $x_i$，表示“停止（-）或恢复（+）城市 $x_i$ 的记忆等级下降过程，从 $t_i$ 年（含）开始”。否则，后面跟着两个整数 $t'_i$ 和 $x'_i$，表示询问“在 $t'_i$ 年年初从城市 $x'_i$ 出发，能遇到的最大记忆等级是多少？”（$0 \le t_i, t'_i \le 10^9$；$1 \le x_i, x'_i \le n$）。

询问按时间顺序给出。保证对于同一城市，- 和 + 操作交替出现，且第一个操作必定是 -。

输出格式

对于每个 ? 询问，输出一行答案。注意，回答时不应考虑后续的 - 和 + 操作。

评分系统

每个子任务的分数仅在通过该子任务及其所需子任务的所有测试时获得。最后一个子任务包含 $16$ 个测试，每个独立得分 $1$ 分。

样例

样例 1

输入：

3 9
5 7 4
1 2
1 3
- 0 3
? 0 1
? 0 2
? 0 3
+ 3 3
- 4 1
? 5 1
? 5 2
? 5 3

输出：

6
7
5
1
2
2

样例 2

输入：

5 9
5 7 4 0 0
1 2
1 3
3 4
3 5
- 0 3
? 0 1
? 0 2
? 0 3
+ 4 3
- 5 1
? 5 1
? 5 2
? 5 3

输出：

6
7
5
2
2
3