Marked Ancestor

Interview

Time limit8sMemory limit512 MB

Summary

On a rooted tree, process mark and query operations where each query asks for the nearest marked ancestor of a node, then report the sum of all query answers.

Level: Medium6 of 10
Topics: Union-find, Tree, DFS, Implementation
Solved: No attempts yet

Problem

You are given a tree T that consists of N nodes. Each node is numbered from 1 to N, and node 1 is always the root of T. Consider the following two operations on T:

M v: (Mark) Mark node v.
Q v: (Query) Print the index of the marked ancestor of node v that is nearest to it. Initially, only the root node is marked. A node is an ancestor of itself.

Write a program that performs a sequence of these operations on a given tree and computes the value that each Q operation will print. To avoid too large an output file, your program must print the sum of the outputs of all query operations. The judges confirmed that every query operation in a given sequence has a well-defined output.

Input

The first line of the input contains two integers N and Q, which denote the number of nodes in the tree T and the number of operations, respectively. These numbers meet the following conditions: 1 ≤ N ≤ 100000 and 1 ≤ Q ≤ 100000.

The following N - 1 lines describe the configuration of the tree T. Each line contains a single integer pi (i = 2, ... , N), which represents the index of the parent of the i-th node.

The next Q lines contain operations in order. Each operation is formatted as "M v" or "Q v", where v is the index of a node.

Output

Print the sum of the outputs of all query operations in one line.

Examples1

Example 1
Input
```
6 3
1
1
2
3
3
Q 5
M 3
Q 5
```
Expected output
```
4
```