Danil decided to earn some money, so he had found a part-time job. The interview have went well, so now he is a light switcher.

Danil works in a rooted tree (undirected connected acyclic graph) with n vertices, vertex 1 is the root of the tree. There is a room in each vertex, light can be switched on or off in each room. Danil's duties include switching light in all rooms of the subtree of the vertex. It means that if light is switched on in some room of the subtree, he should switch it off. Otherwise, he should switch it on.

Unfortunately (or fortunately), Danil is very lazy. He knows that his boss is not going to personally check the work. Instead, he will send Danil tasks using Workforces personal messages.

There are two types of tasks: 

  1. pow v describes a task to switch lights in the subtree of vertex v.
  2. get v describes a task to count the number of rooms in the subtree of v, in which the light is turned on. Danil should send the answer to his boss using Workforces messages.



A subtree of vertex v is a set of vertices for which the shortest path from them to the root passes through v. In particular, the vertex v is in the subtree of v.

Danil is not going to perform his duties. He asks you to write a program, which answers the boss instead of him.

Input

The first line contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n - 1 space-separated integers p2, p3, ..., pn (1 ≤ pi < i), where pi is the ancestor of vertex i.

The third line contains n space-separated integers t1, t2, ..., tn (0 ≤ ti ≤ 1), where ti is 1, if the light is turned on in vertex i and 0 otherwise.

The fourth line contains a single integer q (1 ≤ q ≤ 200 000) — the number of tasks.

The next q lines are get v or pow v (1 ≤ v ≤ n) — the tasks described above.

Output

For each task get v print the number of rooms in the subtree of v, in which the light is turned on.

Example

Input

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


Output

2
0
0
1
2
1
1
0

Note

<image> The tree before the task pow 1.

<image> The tree after the task pow 1.

Difficulty: HARD
Tags: Tree algorithms

Bit manipulation

Data structures
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
class LazySegTree:

	def __init__(self, init_val, seg_ide, lazy_ide, f, g, h):
		self.n = len(init_val)
		self.num = 2 ** (self.n - 1).bit_length()
		self.seg_ide = seg_ide
		self.lazy_ide = lazy_ide
		self.f = f
		self.g = g
		self.h = h
		self.seg = [seg_ide] * 2 * self.num
		for i in range(self.n):
			self.seg[i + self.num] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.seg[i] = self.f(self.seg[2 * i], self.seg[2 * i + 1])
		self.size = [0] * 2 * self.num
		for i in range(self.n):
			self.size[i + self.num] = 1
		for i in range(self.num - 1, 0, -1):
			self.size[i] = self.size[2 * i] + self.size[2 * i + 1]
		self.lazy = [lazy_ide] * 2 * self.num

	def update(self, i, x):
		i += self.num
		self.seg[i] = x
		while i:
			i = i >> 1
			self.seg[i] = self.f(self.seg[2 * i], self.seg[2 * i + 1])

	def calc(self, i):
		return self.g(self.seg[i], self.lazy[i], self.size[i])

	def calc_above(self, i):
		i = i >> 1
		while i:
			self.seg[i] = self.f(self.calc(2 * i), self.calc(2 * i + 1))
			i = i >> 1

	def propagate(self, i):
		self.seg[i] = self.g(self.seg[i], self.lazy[i], self.size[i])
		self.lazy[2 * i] = self.h(self.lazy[2 * i], self.lazy[i])
		self.lazy[2 * i + 1] = self.h(self.lazy[2 * i + 1], self.lazy[i])
		self.lazy[i] = self.lazy_ide

	def propagate_above(self, i):
		H = i.bit_length()
		for h in range(H, 0, -1):
			self.propagate(i >> h)

	def query(self, l, r):
		l += self.num
		r += self.num
		lm = l // (l & -l)
		rm = r // (r & -r) - 1
		self.propagate_above(lm)
		self.propagate_above(rm)
		al = self.seg_ide
		ar = self.seg_ide
		while l < r:
			if l & 1:
				al = self.f(al, self.calc(l))
				l += 1
			if r & 1:
				r -= 1
				ar = self.f(self.calc(r), ar)
			l = l >> 1
			r = r >> 1
		return self.f(al, ar)

	def oprerate_range(self, l, r, a):
		l += self.num
		r += self.num
		lm = l // (l & -l)
		rm = r // (r & -r) - 1
		self.propagate_above(lm)
		self.propagate_above(rm)
		while l < r:
			if l & 1:
				self.lazy[l] = self.h(self.lazy[l], a)
				l += 1
			if r & 1:
				r -= 1
				self.lazy[r] = self.h(self.lazy[r], a)
			l = l >> 1
			r = r >> 1
		self.calc_above(lm)
		self.calc_above(rm)
f = lambda x, y: x + y
g = lambda x, a, s: s - x if a % 2 == 1 else x
h = lambda a, b: a + b

def EulerTour(g, root):
	n = len(g)
	root = root
	g = g
	tank = [root]
	eulerTour = []
	left = [0] * n
	right = [-1] * n
	depth = [-1] * n
	parent = [-1] * n
	child = [[] for i in range(n)]
	eulerNum = -1
	de = -1
	while tank:
		v = tank.pop()
		if v >= 0:
			eulerNum += 1
			eulerTour.append(v)
			left[v] = eulerNum
			right[v] = eulerNum
			tank.append(~v)
			de += 1
			depth[v] = de
			for u in g[v]:
				if parent[v] == u:
					continue
				tank.append(u)
				parent[u] = v
				child[v].append(u)
		else:
			de -= 1
			if ~v != root:
				eulerTour.append(parent[~v])
				eulerNum += 1
				right[parent[~v]] = eulerNum
	return (eulerTour, left, right)
import bisect
import sys
import io, os
input = sys.stdin.readline

def main():
	n = int(input())
	P = list(map(int, input().split()))
	T = list(map(int, input().split()))
	P = [p - 1 for p in P]
	P = [-1] + P
	edge = [[] for i in range(n)]
	for (i, p) in enumerate(P):
		if p != -1:
			edge[p].append(i)
	(et, left, right) = EulerTour(edge, 0)
	d = {}
	B = sorted(left)
	for (i, b) in enumerate(B):
		d[b] = i
	A = [0] * n
	for i in range(n):
		A[d[left[i]]] = T[i]
	seg = LazySegTree(A, 0, 0, f, g, h)
	q = int(input())
	for i in range(q):
		query = list(map(str, input().split()))
		if query[0] == 'get':
			u = int(query[1]) - 1
			l = d[left[u]]
			r = bisect.bisect_right(B, right[u])
			print(seg.query(l, r))
		else:
			u = int(query[1]) - 1
			l = d[left[u]]
			r = bisect.bisect_right(B, right[u])
			seg.oprerate_range(l, r, 1)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from math import inf, log2

class LazySegmentTree:

	def __init__(self, array, func=max):
		self.n = len(array)
		self.size = 2 ** (int(log2(self.n - 1)) + 1) if self.n != 1 else 1
		self.func = func
		self.default = 0
		self.data = [self.default] * (2 * self.size)
		self.segsize = [0] * (2 * self.size)
		self.lazy = [0] * (2 * self.size)
		self.process(array)

	def process(self, array):
		self.data[self.size:self.size + self.n] = array
		self.segsize[self.size:self.size + self.n] = [1] * len(array)
		for i in range(self.size - 1, -1, -1):
			self.data[i] = self.data[2 * i] + self.data[2 * i + 1]
			self.segsize[i] = self.segsize[2 * i] + self.segsize[2 * i + 1]

	def push(self, index):
		self.lazy[2 * index] += self.lazy[index]
		self.lazy[2 * index + 1] += self.lazy[index]
		if self.lazy[index] % 2:
			self.data[index] = self.segsize[index] - self.data[index]
		self.lazy[index] = 0

	def build(self, index):
		index >>= 1
		while index:
			(left, right) = (self.data[2 * index], self.data[2 * index + 1])
			if self.lazy[2 * index] % 2:
				left = self.segsize[2 * index] - left
			if self.lazy[2 * index + 1] % 2:
				right = self.segsize[2 * index + 1] - right
			self.data[index] = left + right
			index >>= 1

	def query(self, alpha, omega):
		res = self.default
		alpha += self.size
		omega += self.size + 1
		for i in range(len(bin(alpha)[2:]) - 1, 0, -1):
			self.push(alpha >> i)
		for i in range(len(bin(omega - 1)[2:]) - 1, 0, -1):
			self.push(omega - 1 >> i)
		while alpha < omega:
			if alpha & 1:
				if self.lazy[alpha] % 2:
					res += self.segsize[alpha] - self.data[alpha]
				else:
					res += self.data[alpha]
				alpha += 1
			if omega & 1:
				omega -= 1
				if self.lazy[omega] % 2:
					res += self.segsize[omega] - self.data[omega]
				else:
					res += self.data[omega]
			alpha >>= 1
			omega >>= 1
		return res

	def update(self, alpha, omega):
		alpha += self.size
		omega += self.size + 1
		(l, r) = (alpha, omega)
		for i in range(len(bin(alpha)[2:]) - 1, 0, -1):
			self.push(alpha >> i)
		for i in range(len(bin(omega - 1)[2:]) - 1, 0, -1):
			self.push(omega - 1 >> i)
		while alpha < omega:
			if alpha & 1:
				self.lazy[alpha] += 1
				alpha += 1
			if omega & 1:
				omega -= 1
				self.lazy[omega] += 1
			alpha >>= 1
			omega >>= 1
		self.build(l)
		self.build(r - 1)

def dfs(graph, alpha):
	n = len(graph)
	visited = [False] * n
	finished = [False] * n
	dp = [0] * n
	subtree = [0] * n
	order = []
	stack = [alpha]
	while stack:
		v = stack[-1]
		if not visited[v]:
			visited[v] = True
			for u in graph[v]:
				if not visited[u]:
					stack.append(u)
		else:
			order += [stack.pop()]
			dp[v] = switch[v] == 1
			subtree[v] = 1
			for child in graph[v]:
				if finished[child]:
					dp[v] += dp[child]
					subtree[v] += subtree[child]
			finished[v] = True
	return (dp, order[::-1], subtree)
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	switch = [0] + list(map(int, input().split()))
	graph = [[] for i in range(n + 1)]
	for i in range(len(a)):
		(x, y) = (i + 2, a[i])
		graph[x] += [y]
		graph[y] += [x]
	(dp, order, subtree) = dfs(graph, 1)
	index = [0] * (n + 1)
	for i in range(len(order)):
		index[order[i]] = i + 1
	st = LazySegmentTree([0] * (n + 1), func=lambda a, b: a + b)
	for i in range(1, n + 1):
		if switch[i]:
			st.update(index[i], index[i])
	for __ in range(int(input())):
		s = input().split()
		x = int(s[1])
		count = subtree[x]
		if s[0] == 'get':
			print(st.query(index[x], index[x] + count - 1))
		else:
			st.update(index[x], index[x] + count - 1)