Christmas Tree Ornament

Byteland Party Factory is preparing to launch a new Christmas-tree ornament. To build the prototype, two lamps were first connected to each other with a wire, and then, $(N - 2)$ times, a new lamp was taken and connected with a wire to one of the already existing lamps. The result is an ornament made of $N$ colored lamps. The factory stocks $K$ different lamp colors.

Once the first prototype was ready, it was handed over to the decoration department. There it was decided that a good measure of the ornament's beauty is the number of wires that connect two lamps of the same color. The department then replaced one existing lamp with another $M$ times, and after each replacement they wanted to know the beauty of the resulting ornament.

Write a program that, given the ornament's initial prototype and the list of replacements made by the decoration department, computes the beauty of the ornament after each replacement.

The first line of the input contains three integers: the number of lamps in the ornament $N$ ($2 \le N \le 300\,000$), the number of replacements made by the decoration department $M$ ($1 \le M \le 300\,000$), and the number of possible lamp colors $K$ ($1 \le K \le 10^9$).

The second line contains $N$ integers $A_i$ ($1 \le A_i \le K$), giving the colors of the lamps in the order they were added to the ornament.

The third line contains $N - 2$ integers $P_i$ ($1 \le P_i \le i + 1$), where $P_i$ tells which lamp the lamp numbered $(i + 2)$ was connected to.

Each of the following $M$ lines contains two integers $X_i$ and $Y_i$ ($1 \le X_i \le N$, $1 \le Y_i \le K$), meaning that in the $i$-th replacement the lamp $X_i$ was replaced by a lamp of color $Y_i$.

The lamps are numbered $1$ to $N$ in the order they were added; lamps $1$ and $2$ are the initial pair joined by a wire.

Output exactly $M$ lines. On line $i$, print the number of lamp pairs that are joined by a wire and have the same color in the configuration after the $i$-th replacement.