Danil and a Part-time Job

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

Each vertex is a room whose light is either on or off. The command pow v flips every light in the subtree of $v$, and get v asks how many lights are on in that subtree.

Input

The first line contains $n$. The second line contains the parents $p_2,\ldots,p_n$; it is empty when $n=1$. The third line contains the $n$ initial light states. The fourth line contains $q$. The next $q$ lines contain either pow v or get v.

Output

For every get command, print the number of lights that are on in the subtree.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$.
• Every light state is 0 or 1.

Example

Input

1

0
8
pow 1
get 1
pow 1
get 1
pow 1
pow 1
get 1
get 1

Output

1
0
0
0

Explanation

Each pow 1 flips the only light, and each get 1 prints its current state.