题目描述

WC2014 后无数人来膜拜 jc，但是来膜拜的人实在太多了， 而且很多人是一连膜拜好几天。所以 jc 给这些人建了一座树形的宿舍，而根节点（$1$ 号节点）住着 jc。然而，由于设计的原因，宿舍中只有一个水龙头。于是晚上打水就成了问题。

所有人都有一个大小不同的水桶，第 $i$ 个结点住着的人的水 桶灌满要 $T_i$ 的时间。水龙头一开始在 jc 的宿舍，但是水龙头的位置会发生变化。当一个人去打水，他走的一定是到水龙头的最短距离，而且他路过的所有宿舍中住的人都会和他 一起去打水。现在有 $n$ 个人入住，发生了 $m$ 个事件：

1. C i 表示水龙头在第 $i$ 个宿舍
2. Q i 表示住在 $i$ 宿舍的人出发去打水。

对于每个 $Q$ 操作，你需要告诉 jc 这次去打水的所有人最少的总等待时间。

输入格式

第一行三个整数 $n,m,key$

接下来一行 $n$ 个整数，表示 $T_i$（小于等于 $10^7$）

接下来一行 $n$ 个数，表示每个节点的父亲，保证根节点的父亲为 $0$

接下来 $m$ 行每行表述一个事件:对于每个 $Q$ 操作，若输入为 Q k，则实际的 $k=(k+(pre \bmod 2)*key) \bmod n+1$，pre为上一个询问的答案，若是第一个询问则 $pre=0$。

一开始水龙头在1号节点。

输出格式

对于每个 $Q$ 事件输出一行，为答案。

3 2 0
2 2 1
0 3 1
C 3
Q 1

4 

提示

没有写明提示

题目来源

By jiry_2 XXY杯省选模拟题