给你一棵由 $$$n$$$ 节点组成的树。该树以节点 $$$1$$$ 为根,无论其度数如何,该节点都不被视为叶子。
树的每片叶子都有两种颜色之一:红色或蓝色。叶节点 $$$v$$$ 最初的颜色为 $$$s_{v}$$$。
每个内部节点(包括根)的颜色确定如下。
- 令 $$$b$$$ 为蓝色直接子节点的数量,$$$r$$$ 为给定顶点的红色直接子节点的数量。
- 当且仅当 $$$b - r \ge k$$$ 时,该顶点的颜色为蓝色,否则为红色。
整数 $$$k$$$ 是所有节点都相同的参数。
您需要处理以下类型的查询:
- 1 v:打印节点$$$v$$$的颜色;
- 2 v c:将叶子$$$v$$$的颜色更改为$$$c$$$($$$c = 0$$$表示红色,$$$c = 1$$$表示蓝色);
- 3 h:将 $$$k$$$ 的当前值更新为 $$$h$$$。
输入
输入的第一行由两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^{5}$$$, $$$-n \le k \le n$$$) 组成 - 节点数和初始参数 $$$k$$$。
接下来的 $$$n - 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。
下一行由 $$$n$$$ 空格分隔的整数组成 - 初始数组 $$$s$$$ ($$$-1 \le s_i \le 1$$$)。 $$$s_{i} = 0$$$ 表示节点$$$i$$$ 的颜色为红色。 $$$s_{i} = 1$$$ 表示节点$$$i$$$ 的颜色为蓝色。 $$$s_{i} = -1$$$ 表示节点 $$$i$$$ 不是叶子。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$),即查询次数。
$$$q$$$ 行如下,每行包含以下查询之一中的查询:
- 1 v ($$$1 \le v \le n$$$): 打印节点$$$v$$$的颜色;
- 2 v c ($$$1 \le v \le n$$$, $$$c = 0$$$ 或 $$$c = 1$$$): 将叶子 $$$v$$$ 的颜色更改为 $$$c$$$ ($$$c = 0$$$ 表示红色,$$$c = 1$$$ 表示蓝色)。保证 $$$v$$$ 是叶子;
- 3 h ($$$-n \le h \le n$$$):将 $$$k$$$ 的当前值更新为 $$$h$$$。
输出
对于第一种类型的每个查询,如果顶点 $$$v$$$ 的颜色为红色,则打印 $$$0$$$,否则打印 $$$1$$$。
示例
输入 #1
5 2 1 2 1 3 2 4 2 5 -1 -1 0 1 0 9 1 1 1 2 3 -2 1 1 1 2 3 1 2 5 1 1 1 1 2
输出 #1
0 0 1 1 0 1
注意
图:(i)初始树(ii)第三次查询后的树(iii)第七次查询后的树