罗马尼亚有一道名为“Mici”的特色菜，它是一种用碎肉制成的、没有外皮的厚肉肠。制作 Mici 非常简单，不值一提，但如何正确地烤好它们却是一门艺术，因此我们甚至不打算向你解释这一点。关于 Mici，你需要知道的是，罗马尼亚人对它们非常狂热，以至于他们学会了一种将 Mici 召唤到自己身边的秘诀。此外，每个罗马尼亚人在特定时刻对于自己想吃多少个 Mici 都有一个期望值。

在一个有 $n$ 个至亲参加的传统家庭烧烤聚会上，餐桌已经布置妥当，每个人的盘子里都装有一些 Mici。你可以将餐桌想象成一棵拥有 $n$ 个节点的无根树，每个人坐在其中一个节点上。

作为真正的罗马尼亚人，家庭成员们只关心一件事：他们能分到多少个 Mici。为此，坐在节点 $u$ 的人可以使用魔法秘诀将 Mici 召唤到他们身边；我们将此操作称为 “CJ u”。当使用该秘诀时，其效果是餐桌上的所有 Mici 都会向节点 $u$ 移动一步：位于节点 $v$ 的 Mici 将移动到 $v$ 在树中距离 $u$ 最近的邻居节点。已经在节点 $u$ 的 Mici 则保持原地不动。

每隔一段时间，某个家庭成员会非常强烈地希望自己能恰好吃到 $x$ 个 Mici，因此他们想知道自己的盘子里是否恰好有 $x$ 个 Mici。该操作表示为 “JS u x”，意味着坐在节点 $u$ 的人询问节点 $u$ 处是否恰好有 $x$ 个 Mici。

因为家人们现在饿得无法正常思考，他们请求你帮助回答这些问题。请注意，在本题中，家庭成员并不会真正吃掉 Mici。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$：分别表示家庭成员的数量和餐桌上发生的操作次数（$2 \le n \le 10^5$，$1 \le q \le 10^5$）。

下一行包含一个由 $n$ 个整数组成的数组 $m_1, m_2, \dots, m_n$：表示节点 $1, 2, \dots, n$ 处初始的 Mici 数量（$0 \le m_i \le 10^9$）。餐桌上的 Mici 总数最多为 $10^9$。

接下来的 $n-1$ 行描述了作为树的餐桌布局。每行包含两个整数 $u$ 和 $v$，表示 $u$ 和 $v$ 之间存在一条边（$1 \le u, v \le n$，$u \neq v$）。给定的边构成一棵树。

接下来的 $q$ 行中，每行描述一个可能的操作：

• “CJ u”：坐在节点 $u$ 的人将 Mici 召唤到他们身边（$1 \le u \le n$）。
• “JS u x”：坐在节点 $u$ 的人询问他们的盘子里是否恰好有 $x$ 个 Mici（$1 \le u \le n$，$0 \le x \le 10^9$）。

输出格式

对于每个类型为 “JS” 的询问，输出一行，包含一个整数：如果询问的答案为“是”则输出 $1$，否则输出 $0$。

样例

输入样例 1

6 4
1 1 1 2 2 2
1 2
2 3
2 4
4 5
3 6
CJ 6
CJ 6
JS 6 4
JS 6 3

输出样例 1

1
0