题目描述

热带雨林的地图有 $n$ 个节点，它们由 $n-1$ 条可双向通行的道路连接起来，保证任意两个节点可以通过若干道路相互到达。每个节点有一个安全值 $a_i$，我们认为 $a_i > 0$ 的节点是安全的，$a_i \leq 0$ 的节点是危险的。 小可可时常会想去热带雨林中的某个节点探险。他会从这个节点出发，不经过任何危险节点，去探索尽可能多的节点。他想知道在每次探险中能到达多少个节点，如果初始节点就是危险的，那么他就会放弃探险计划，认为到达了 $0$ 个节点。 小可可一直关注着热带雨林的动态，他注意到，时常会有动物从某个节点沿最短路径迁徙到另外一个节点，并使这条路径上所有节点（包括出发点与到达点）的安全值加上了同一个值。由于有的动物是友善的，有的则不那么友善，所以安全值加上的值可能为正可能为负。 交织着发生了 $q$ 次事件，每个事件形如小可可做了一次去某个节点探险的计划或行动物进行了迁徙，你能帮小可可求出，他的每个探险计划能到达多少个节点吗？

输入格式

第一行两个正整数 $n$ 和 $q$。 接下来一行 $n$ 个正整数，表示每个结点的安全值。 接下来 $n-1$ 行，每行两个正整数 $u_i, v_i$，表示一条道路。 接下来 $q$ 行，每行的第一个数是 $o$，其中 $o \in \{0,1\}$。若 $o = 0$，则表示小可可进行了一次探险计划，接下来一个正整数 $c$，表示小可可计划的节点；若 $o = 1$，则表示有动物进行了迁徙，接下来三个正整数 $x, y, d$，表示迁徙的出发点、到达点以及对路径上每个节点安全值的增加量。

输出格式

对于每个小可可的探险计划，输出一行，表示能到达多少个节点。

样例 1 输入

8 12 3 -9 7 2 5 0 8 1 1 2 1 3 3 4 3 5 3 6 6 7 6 8 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 1 1 8 2 0 5 1 1 8 -1 0 8

样例 1 输出

4 0 4 4 4 0 1 1 7 7

数据规模与约定

对于所有数据，有 $n, q \leq 2 \times 10^5$，$-10^4 \leq a_i, d \leq 10^4$，$1 \leq u_i, v_i, x, y \leq n$； 对于测试点 $1 \sim 2$，$1 \leq n, q \leq 2000$； 对于测试点 $3 \sim 4$，$o = 0$； 对于测试点 $5 \sim 7$，$u_i = i, v_i = i + 1$； 对于测试点 $8 \sim 10$，$d > 0$； 对于测试点 $11 \sim 14$，$x = y$； 对于测试点 $15 \sim 17$，$c = 1$； 对于测试点 $18 \sim 20$，无特殊限制。