丹尼尔决定赚点钱,所以他找到了一份兼职工作。面试很顺利,所以现在他是一名灯光开关师。
Danil 在一个有 n 个顶点的有根树(无向连通无环图)中工作,顶点 1 是树的根。每个顶点都有一个房间,每个房间的灯都可以打开或关闭。 Danil 的职责包括切换顶点子树所有房间的灯光。这意味着如果子树的某个房间的灯打开了,他应该将其关闭。否则,他应该打开它。
不幸的是(或者幸运的是),丹尼尔非常懒。他知道他的老板不会亲自检查工作。相反,他将使用 Workforces 个人消息向 Danil 发送任务。
有两种类型的任务:
1. pow v 描述了一个在顶点 v 的子树中开关灯的任务。
2. get v 描述了一个计算 v 子树中灯打开的房间数量的任务。丹尼尔应该使用劳动力消息将答案发送给他的老板。
顶点v的子树是从它们到根的最短路径经过v的顶点的集合。特别地,顶点v位于v的子树中。
丹尼尔不会履行他的职责。他要求你写一个程序,由它代替他回答老板。
输入
第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 树中的顶点数。
第二行包含 n - 1 个空格分隔的整数 p2, p3, ..., pn (1 ≤ pi < i),其中 pi 是顶点 i 的祖先。
第三行包含 n 个空格分隔的整数 t1, t2, ..., tn (0 ≤ ti ≤ 1),其中如果灯在顶点 i 打开,则 ti 为 1,否则为 0。
第四行包含一个整数 q (1 ≤ q ≤ 200 000) — 任务数。
接下来的 q 行是 get v 或 pow v (1 ≤ v ≤ n) — 上面描述的任务。
输出
对于每个任务 get v 打印 v 子树中灯打开的房间数。
示例
输入 #1
4 1 1 1 1 0 0 1 9 get 1 get 2 get 3 get 4 pow 1 get 1 get 2 get 3 get 4
输出 #1
2 0 0 1 2 1 1 0
注意
任务 pow 1 之前的树。任务 pow 1 之后的树。