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 node of T. Consider the following two operations on T:

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



Your job is to write a program that performs a sequence of these operations on a given tree and calculates the value that each Q operation will print. To avoid too large output file, your program is requested to print the sum of the outputs of all query operations. Note that the judges confirmed that it is possible to calculate every output of query operations in a given sequence.



Input

The input consists of multiple datasets. Each dataset has the following format:

The first line of the input contains two integers N and Q, which denotes 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 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.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the sum of the outputs of all query operations in one line.

Example

Input

6 3
1
1
2
3
3
Q 5
M 3
Q 5
0 0


Output

4

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def root(x):
	while P[x] != x:
		x = P[x]
	return x

def mark(x):
	P[x - 1] = x - 1

def query(x):
	v = root(x - 1) + 1
	return v
while True:
	(N, Q) = map(int, input().strip().split(' '))
	if N == Q == 0:
		break
	P = []
	P.append(0)
	for i in range(N - 1):
		p_i = int(input().strip()) - 1
		P.append(p_i)
	s = 0
	for j in range(Q):
		op = input().strip().split(' ')
		if op[0] == 'M':
			mark(int(op[1]))
		else:
			s += query(int(op[1]))
	print(s)


def solve():
	import sys
	file_input = sys.stdin
	while True:
		(N, Q) = map(int, file_input.readline().split())
		if N == 0:
			break
		parent = [None, None]
		parent += [int(file_input.readline()) for _ in range(N - 1)]
		unmarked = [True] * (N + 1)
		unmarked[1] = False
		ans = 0
		for _ in range(Q):
			line = file_input.readline()
			v = int(line[2:])
			if line[0] == 'M':
				unmarked[v] = False
			else:
				while unmarked[v]:
					v = parent[v]
				ans += v
		print(ans)
solve()


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def unite(self, x, y):
		y = self.find(y)
		x = self.find(x)
		self.parents[y] += self.parents[x]
		self.parents[x] = y

	def same(self, x, y):
		return self.find(x) == self.find(y)

def solve(N, Q):
	parents = [-1] * N
	for i in range(1, N):
		p = int(input()) - 1
		parents[i] = p
	query = []
	mark = [0] * N
	mark[0] = 1
	for _ in range(Q):
		q = input().split()
		v = int(q[1]) - 1
		if q[0] == 'M':
			mark[v] += 1
			query.append((0, v))
		else:
			query.append((1, v))
	uf = UnionFind(N)
	for i in range(N):
		if mark[i] == 0:
			uf.unite(i, parents[i])
	ans = 0
	for (ty, v) in query[::-1]:
		if ty == 0:
			mark[v] -= 1
			if mark[v] == 0:
				uf.unite(v, parents[v])
		else:
			ans += uf.find(v) + 1
	print(ans)

def main():
	while True:
		(N, M) = map(int, input().split())
		if N == 0:
			return
		solve(N, M)
main()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 13
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

class UnionFind:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			self.table[s2] += self.table[s1]
			self.table[s1] = s2
			return True
		return False

	def subsetall(self):
		a = []
		for i in range(len(self.table)):
			if self.table[i] < 0:
				a.append((i, -self.table[i]))
		return a

def main():
	rr = []

	def f(n, q):
		ps = [0, 1] + [I() for _ in range(n - 1)]
		qs = []
		ms = set()
		for i in range(q):
			(s, t) = LS()
			t = int(t)
			if s == 'M':
				if t in ms:
					continue
				ms.add(t)
			qs.append((s, t))
		uf = UnionFind(n + 1)
		for i in range(2, n + 1):
			if i in ms:
				continue
			uf.union(i, ps[i])
		r = 0
		for (s, t) in qs[::-1]:
			if s == 'Q':
				r += uf.find(t)
			else:
				uf.union(t, ps[t])
		return r
	while 1:
		(n, q) = LI()
		if n == 0 and q == 0:
			break
		rr.append(f(n, q))
	return '\n'.join(map(str, rr))
print(main())


class UnionFind:

	def __init__(self, size):
		self.parent = list(range(size))

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		self.parent[x] = y

	def same(self, x, y):
		return self.find(x) == self.find(y)
while True:
	(N, Q) = map(int, input().split())
	if N == Q == 0:
		break
	parent = [0, 1] + [int(input()) for i in range(2, N + 1)]
	queries = []
	marked = set([1])
	for i in range(Q):
		(o, v) = input().split()
		v = int(v)
		if o == 'M':
			if v in marked:
				continue
			marked.add(v)
		queries.append((o, v))
	uf = UnionFind(N + 1)
	for i in range(1, N + 1):
		if i not in marked:
			uf.unite(i, parent[i])
	ans = 0
	for (o, v) in reversed(queries):
		if o == 'M':
			uf.unite(v, parent[v])
		else:
			ans += uf.find(v)
	print(ans)


class UnionFind:

	def __init__(self, size):
		self.table = [None] * size

	def find(self, x):
		if self.table[x] == None:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, parent, child):
		p_root = self.find(parent)
		c_root = self.find(child)
		if p_root != c_root:
			self.table[c_root] = p_root

def solve():
	import sys
	input_lines = sys.stdin.readlines()
	while True:
		(N, Q) = map(int, input_lines[0].split())
		if N == 0:
			break
		parent = [0, 1] + list(map(int, input_lines[1:N]))
		unmarked = [True] * (N + 1)
		unmarked[1] = False
		operation = []
		for o in input_lines[N:N + Q]:
			(mq, v) = o.split()
			v = int(v)
			if mq == 'M':
				if unmarked[v]:
					unmarked[v] = False
					operation.append((mq, v))
			else:
				operation.append((mq, v))
		uf = UnionFind(N + 1)
		for (v, p) in enumerate(parent[2:], start=2):
			if unmarked[v]:
				uf.union(p, v)
		ans = 0
		for (mq, v) in reversed(operation):
			if mq == 'M':
				uf.union(parent[v], v)
			else:
				ans += uf.find(v)
		print(ans)
		del input_lines[:N + Q]
solve()


class UnionFind:

	def __init__(self, size):
		self.table = [None] * size

	def find(self, x):
		if self.table[x] == None:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, parent, child):
		p_root = self.find(parent)
		c_root = self.find(child)
		if p_root != c_root:
			self.table[c_root] = p_root

def solve():
	import sys
	input_lines = sys.stdin.readlines()
	while True:
		(N, Q) = map(int, input_lines[0].split())
		if N == 0:
			break
		unmarked = [True] * (N + 1)
		unmarked[1] = False
		operation = []
		for o in input_lines[N:N + Q]:
			(mq, v) = o.split()
			v = int(v)
			if mq == 'M':
				if unmarked[v]:
					unmarked[v] = False
					operation.append((mq, v))
			else:
				operation.append((mq, v))
		uf = UnionFind(N + 1)
		parent = [None, 1] + list(map(int, input_lines[1:N]))
		for (v, p) in enumerate(parent[2:], start=2):
			if unmarked[v]:
				uf.union(p, v)
		ans = 0
		for (o, v) in reversed(operation):
			if o == 'M':
				uf.union(parent[v], v)
			else:
				ans += uf.find(v)
		print(ans)
		del input_lines[:N + Q]
solve()


import sys
sys.setrecursionlimit(10 ** 6)

class UnionFindTree:

	def __init__(self, n):
		self.par = list(range(n))
		self.rank = [0] * n

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)
while True:
	(N, Q) = map(int, input().split())
	if N == Q == 0:
		break
	parents = [0] + [int(input()) - 1 for _ in range(N - 1)]
	queries = []
	marked = set()
	for _ in range(Q):
		(k, v) = input().split()
		v = int(v) - 1
		if k == 'Q':
			queries.append((k, v))
		elif k == 'M' and v not in marked:
			marked.add(v)
			queries.append((k, v))
	uf = UnionFindTree(N)
	for i in range(1, N):
		if i not in marked:
			p_root = uf.find(parents[i])
			uf.par[i] = p_root
			uf.rank[p_root] = max(uf.rank[p_root], uf.par[i] + 1)
	ans = 0
	for (k, v) in reversed(queries):
		if k == 'Q':
			ans += uf.find(v) + 1
		elif not uf.same(v, parents[v]):
			p_root = uf.find(parents[v])
			uf.par[v] = p_root
			uf.rank[p_root] = max(uf.rank[p_root], uf.par[v] + 1)
	print(ans)


def root(x):
	while P[x - 1] != x:
		x = P[x - 1]
	return x

def mark(x):
	P[x - 1] = x
while True:
	(n, q) = map(int, input().split())
	res = 0
	if n == 0:
		break
	P = [1]
	for _ in range(n - 1):
		P.append(int(input()))
	for _ in range(q):
		(com, num) = map(str, input().split())
		if com == 'Q':
			res += root(int(num))
		else:
			mark(int(num))
	print(res)