题目描述

波托科兰迪亚有 $n$ 家面包店，编号为 $1$ 到 $n$。其中第 $i$ 家面包店的仓库里一开始有 $a_i$ 个馅饼。

这些面包店之间有 $n-1$ 条道路，第 $i$ 条道路连接面包店 $u_i$ 与 $v_i$。保证任意两家面包店之间恰好有一条简单路径。

由于波托科兰迪亚经常发生地震，有些道路会被破坏，无法通行，也无法运输馅饼。有时道路维修部门会修复某些道路，使它们重新可以通行。因此，每条道路始终处于两种状态之一：

• 未封闭：可以通行；
• 封闭：不能通行。

定义面包店 $u$ 的连通块为：所有可以从面包店 $u$ 出发，只经过未封闭道路到达的面包店集合。面包店 $u$ 本身也属于自己的连通块。

波托科兰迪亚最著名的居民之一是哥萨克·乌斯。他因为在一年一度的馅饼爱好者节日中吃掉最多馅饼而出名。

现在会发生 $m$ 个事件。你需要依次处理这些事件，并对其中若干事件输出答案。

共有 $7$ 种事件：

1. 改变编号为 $p$ 的道路的状态。若该道路原来封闭，则变为未封闭；若原来未封闭，则变为封闭。
2. 向面包店 $p$ 所在连通块中的每一家面包店仓库都运入 $w$ 个馅饼。也就是说，对每个属于该连通块的面包店 $u$，令 $a_u := a_u + w$。
3. 面包店 $p$ 所在连通块中的所有面包店都把自己的全部馅饼运到面包店 $p$ 的仓库。操作之后，面包店 $p$ 存有该连通块中所有馅饼的总数，而该连通块中其他面包店的仓库均为空。
4. 哥萨克·乌斯询问面包店 $p$ 的仓库中有多少个馅饼，即 $a_p$。
5. 哥萨克·乌斯询问面包店 $p$ 所在连通块中所有面包店仓库里的馅饼总数。
6. 哥萨克·乌斯吃掉面包店 $p$ 所在连通块中每一家面包店仓库里的所有馅饼。操作之后，该连通块中所有面包店的 $a_u$ 都变为 $0$。
7. 哥萨克·乌斯想知道：如果他可以从任意一家面包店出发，并且只能沿未封闭道路移动，那么为了吃掉波托科兰迪亚所有仓库中现有的馅饼，最少需要修复多少条道路。

注意，事件类型 $4,5,7$ 只要求输出答案，不会改变道路或面包店状态。

输入格式

本 Hydro 版本按照官方测试数据格式配置，第一行顺序为 g n m。标程同时兼容原公开题面中的 n m g 顺序。

第一行包含三个整数 $g,n,m$（$0\le g\le 11$，$1\le n,m\le 250000$），分别表示测试点所属子任务编号、面包店数量和事件数量。

接下来 $n-1$ 行，第 $i$ 行包含两个整数 $u_i,v_i$（$1\le u_i,v_i\le n$），表示编号为 $i$ 的道路连接的两家面包店。保证整张图是一棵树。

接下来一行包含一个长度为 $n-1$ 的 01 字符串。第 $i$ 个字符为 1 表示第 $i$ 条道路一开始是封闭的，为 0 表示未封闭。

接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i\le 10^5$），表示每家面包店仓库中一开始的馅饼数量。

接下来 $m$ 行，每行描述一个事件：

• 1 p：改变编号为 $p$ 的道路状态，$1\le p\le n-1$；
• 2 p w：向面包店 $p$ 所在连通块中每家面包店加入 $w$ 个馅饼，$1\le p\le n$，$0\le w\le 10^5$；
• 3 p：将面包店 $p$ 所在连通块中所有馅饼运到面包店 $p$；
• 4 p：询问 $a_p$；
• 5 p：询问面包店 $p$ 所在连通块中的馅饼总数；
• 6 p：清空面包店 $p$ 所在连通块中所有馅饼；
• 7：询问最少需要修复多少条道路，才能吃掉所有现有馅饼。

输出格式

对于每个类型为 $4,5,7$ 的事件，输出一行一个整数，表示答案。

样例

由于官方测试数据第一行采用 g n m 顺序，下面样例也按本 Hydro 版本格式给出。

0 5 11
1 2
1 3
3 4
3 5
0100
1 0 6 1 3
5 3
3 4
2 5 4
4 3
7
6 4
1 2
5 4
2 2 1
1 3
5 2

10
4
1
1
5

样例解释

在图中，面包店用圆圈表示，圆圈内有两个整数：面包店编号和该面包店仓库中的馅饼数量。未封闭道路用实线表示，封闭道路用虚线表示。

初始时，第 $2$ 条道路，即连接面包店 $1$ 和 $3$ 的道路是封闭的。面包店 $1$ 的连通块与面包店 $2$ 的连通块都包含面包店 $1,2$。面包店 $3,4,5$ 的连通块包含面包店 $3,4,5$，因此面包店 $3$ 所在连通块中的馅饼总数为 $6+1+3=10$。

第二个事件后，面包店 $3$ 和 $5$ 把自己的馅饼运到面包店 $4$ 的仓库。

第三个事件后，面包店 $3,4,5$ 的仓库各加入 $4$ 个馅饼，因此面包店 $3$ 的仓库中有 $4$ 个馅饼。此时除面包店 $2$ 外，每家面包店都至少有 $1$ 个馅饼。如果哥萨克·乌斯从面包店 $1$ 或 $2$ 出发，他必须修复第 $2$ 条道路才能到达面包店 $3$；如果他从面包店 $3,4,5$ 中任意一家出发，也必须修复第 $2$ 条道路才能到达面包店 $1$。因此类型 $7$ 询问的答案为 $1$。

第六个事件后，哥萨克·乌斯吃掉面包店 $3,4,5$ 仓库中的所有馅饼。

第七个事件后，道路维修部门修复第 $2$ 条道路，因此整棵树重新连通。此时面包店 $4$ 所在连通块包含所有面包店，所以第八个事件的答案为 $0+1+0+0+0=1$。

第九个事件后，面包店 $1,2,3,4,5$ 的仓库各加入 $1$ 个馅饼。

第十个事件后，第 $3$ 条道路被地震破坏，变为封闭。此时面包店 $1$ 所在连通块包含除面包店 $4$ 外的所有面包店，而面包店 $4$ 单独形成一个连通块。因此最后一次询问答案为 $2+1+1+1=5$。

原题样例含示意图，整理为 Hydro 题面时请按需插入下列图片：

数据范围与子任务

所有测试满足：

$1\le n,m\le 250000$，$0\le g\le 11$，$0\le a_i\le 10^5$，$0\le w\le 10^5$。

子任务如下：

时间与空间限制

• 时间限制：$3\ \mathrm{s}$
• 空间限制：$512\ \mathrm{MB}$