AC Automaton

JB is trying to get more "AC" on problems with his AC Automaton.

The AC Automaton is a rooted tree with $n$ nodes and node 1 as root. Each node $i$ except the root has its unique parent $p\_i$ and a character $s\_i$ on it, which is one of 'A', 'C', or '?'. A node $x$ is called an ancestor of $y$ if and only if $x = p\_y$ or $x$ is an ancestor of $p\_y$. The number of "AC" JB can get is equal to the number of ordered pairs $(x,y)$ such that $x$ is an ancestor of $y$, $s\_x$ is 'A', and $s\_y$ is 'C'. JB can replace each '?' with 'A' or 'C'. His goal is to get more "AC" after replacing all '?'.

However, the problem keeps changing. JB will change his AC Automaton $q$ times. Each time, he modifies the character on one node $x$ to 'A', 'C', or '?' (the character may stay the same). After each modification, find the maximum number of "AC" he can get if he replaces all '?' characters. JB does not actually modify the AC Automaton while calculating this maximum. See the sample for an example.

The first line contains two integers $n$ and $q$ ($1\le n, q\le 300\ 000$).

The second line contains a string of $n$ characters, representing the character on each node. Every character is one of 'A', 'C', and '?'.

The third line contains $n - 1$ integers. The $i$-th integer $p\_i$ ($1\le p\_i \le i$) is the parent of node $i+1$.

The next $q$ lines describe the modifications. The $i$-th of these lines contains an integer $x$ ($1\le x\le n$) and a character $y$ ($y$ is one of 'A', 'C', '?'), meaning node $x$ is set to $y$.

Output $q$ lines. The $i$-th line contains one integer, the maximum number of "AC" after the $i$-th modification.

After the first modification, one of the best ways to replace the characters is "ACCCC", and it has 4 pairs: (1,2), (1,3), (1,4), and (1,5).

After the second modification, one of the best ways to replace the characters is "ACCAC", and it has 3 pairs: (1,2), (1,3), and (1,5).

After the third modification, one of the best ways to replace the characters is "AACAC", and it has 3 pairs: (1,3), (2,3), and (1,5).