为了夺取海克斯科技之门并完成他那伟大的进化，维克托正在进攻皮尔特沃夫。皮尔特沃夫有 $n$ 个路口，由 $n - 1$ 条双向道路连接，使得任意两个路口之间都可以通过这些道路互相到达。换句话说，皮尔特沃夫是一棵树。

维克托使用他的海克斯科技之爪发射海克斯射线来攻击皮尔特沃夫，而杰斯发明了海克斯护盾来保护城市。每次攻击都有一个伤害值，每个海克斯护盾都有一个生命值。当伤害值为 $a$ 的攻击击中生命值为 $b$ 的海克斯护盾时，护盾的生命值会减少到 $b - a$。如果海克斯护盾的生命值小于或等于零，则该海克斯护盾被视为被摧毁。

当海克斯护盾受到攻击时，它可以进行过载以将伤害减半，这意味着伤害值可能是一个实数。例如，如果初始伤害为 $3$ 且护盾过载，则实际伤害为 $1.5$。然而，海克斯护盾不能在连续两次受到的攻击中都进行过载，因为这会导致海克斯宝石变得不稳定，从而产生灾难性的后果。

在维克托的猛烈攻击下，杰斯制造了许多海克斯护盾，并将它们部署在路口以阻挡即将到来的伤害。一旦部署了海克斯护盾，它将吸收所有针对该路口的攻击伤害。现在按顺序发生了 $q$ 个事件：

• A x y z：维克托发射海克斯射线，攻击从 $x$ 到 $y$ 的最短路径上的所有路口，伤害值为 $z$。
• D x h：杰斯在路口 $x$ 探测到一个尚未被摧毁的海克斯护盾。由于战场上的混乱，杰斯不记得这个海克斯护盾是什么时候放置的。他只记得海克斯护盾的初始生命值为 $h$。你需要帮助他计算该护盾所能承受的最大攻击次数，以帮助杰斯推断该海克斯护盾的可靠性。

防御绝不能失败，所以请帮助杰斯完成计算。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n \le 5 \cdot 10^5, 1 \le q \le 3 \cdot 10^5$)，分别表示路口的数量和事件的数量。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示连接路口 $u$ 和 $v$ 的一条双向边。

接下来的 $q$ 行，每行描述一个事件，以字符 $o_i$ ($o_i \in \{A, D\}$) 开头。如果 $o_i = A$，则后面跟着三个整数 $x_i, y_i, z_i$ ($1 \le x_i, y_i \le n, 1 \le z_i \le 370$)，描述一个攻击事件。否则，后面跟着两个整数 $x_i, h_i$ ($1 \le x_i \le n, 1 \le h_i \le 10^9$)，描述一个探测事件。

输出格式

对于每个探测类型的事件，输出一行答案。

样例

输入 1

5 7
1 2
1 3
2 4
2 5
A 1 4 2
A 3 5 2
D 1 4
D 2 3
D 2 1
A 5 5 10
D 5 100

输出 1

2
1
0
2