Description

δ-me13 眼中，桃子是充满美好的事物。

PhiLia093 给了 δ-me13 一棵有 $n$ 个节点的树。每个节点初始时没有或有一个桃子。有桃子的节点是粉色（用 P 表示），没有桃子的节点是白色（用 W 表示）。每个节点还有一个权值 $a_i$ ，初始 $a$ 全为 $0$ 。进行 $q$ 次操作，操作有以下三种。

1. 给出点 $u$ 。若 $u$ 是 W，则把 $u$ 变成 P，即放一个桃子；若 $u$ 是 P，则把 $u$ 变成 W，即拿走一个桃子。

2. 给出点 $u$ 和 $x$。对于所有的点 $v$（$u$ 可能等于 $v$），若 $u$ 到 $v$ 的最短路径上（包括 $u$ 和 $v$），有且仅有一个 P，则 $a_v\gets a_v+x$。 δ-me13 想要吃桃子，但她只能吃下一个。

3. 给出点 $u$ ，询问 $a_u$ 。

但是 δ-me13 已经回到翁法罗斯的过去了，在离开前也没解出答案，所以她将这个问题托付给你。

她会停留在扉页，等待你续写新的起点。

题外话：要不是空间开不下，我想弄一个 $n=33550337$ 的点。

Input Format

第一行三个整数 $n,q$，表示树的结点个数、操作次数。

第二行一个长度为 $n$ 的、由字符 W 和 P 组成的字符串，表示每个节点初始时有没有桃子。

接下来一行 $n-1$ 个整数，第 $i$ 个为 $fa_{i+1}$。其中，$fa_u$ 表示 $u$ 的父亲节点编号。

接下来 $q$ 行，每行描述一个操作。形如以下三种：

• 1 u

• 2 u x

• 3 u

Output Format

对于每个操作三，输出一行一个整数，表示答案。

10 12
WWPWPPWWPP
1 2 3 3 2 6 2 1 9
1 5
2 8 1
3 1
3 2
3 3
3 6
3 8
3 4
3 5
3 7
3 9
3 10

0
0
1
1
0
1
1
1
1
0

10 15
WWPWPPWWPP
1 2 3 3 2 6 2 1 9
2 1 1
2 3 2
2 7 1
2 6 1
3 3
3 8
3 6
1 3
1 9
1 2
2 5 2
2 9 1
3 1
3 9
3 4

3
4
3
4
1
6

Hint

特殊性质 A：没有操作 1。

特殊性质 B：对于操作 1，保证 $u$ 在操作前颜色都是 W。

特殊性质 C：对于操作 1，保证 $u$ 在操作前颜色都是 P。

对于所有数据，满足 $1\le n,q\le 10^6$ , $1\le x\le 10^3$ 。

保证时间与空间限制均为 std 的 2 倍以上。