#3460. Jc的宿舍

内存限制:512 MiB 时间限制:130 Sec

题目描述

WC2014后无数人来膜拜jc,但是来膜拜的人实在太多了, 而且很多人是一连膜拜好几天。所以jc给这些人建了一座树 形的宿舍,而根节点(1号节点)住着jc。然而,由于设计 的原因,宿舍中只有一个水龙头。于是晚上打水就成了问题。 所有人都有一个大小不同的水桶,第i个结点住着的人的水 桶灌满要Ti的时间。水龙头一开始在jc的宿舍,但是水龙 头的位置会发生变化。当一个人去打水,他走的一定是到水 龙头的最短距离,而且他路过的所有宿舍中住的人都会和他 一起去打水。现在有n个人入住,发生了m个事件。

1.C i 表示水龙头在第i个宿舍

2.Q i 表示住在i宿舍的人出发去打水。

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

输入格式

第一行三个整数n,m,key,接下来一行n个整数 表示Ti(小于等于10^7),接下来一行n个数表示每个节点 的父亲,保证根节点的父亲为0。接下来m行每行表述一个 事件。对于每个Q操作,若输入为Q k,则实际的k=(k+(pre mod 2)*key) mod n+1,pre为上一个询问的答案,若是第一个 询问则pre=0。一开始水龙头在1号节点。

输出格式

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

样例

样例输入


			

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

样例输出


			
4

数据范围与提示

 N<=50000,M<=50000,Key<=10^9