La mayoría de las personas decora los árboles de navidad con guirnaldas de bombillos lumínicos para el año nuevo, pero solo unos pocos saben que es posible también usar guirnarldas luminosas para cualquier día festivo.

El primer modelo de decoraciones luminosas con diferentes colores fue construido por la Fábrica de Festividades de IslaGrande. El prototipo se describe como sigue: primeramente ellos toman dos bombillas y las conectan con un cable, luego \(N–2\) veces ellos toman una bombilla y la conectan usando un cable a alguna de las bombillas ya conectadas previamente a la guirnalda. Como resultado para la decoración se obtiene una guirnalda de ~N~ bombillas de colores. En la fábrica hay ~K~ colores distintos disponibles para aplicarle a las bombillas lumínicas.

Cuando el prototipo está listo, es transferido al Departamento de Belleza. En este departamento se considera la belleza de la decoración como el número de pares de bombillas del mismo color conectadas por un cable. El staff de este departamento repinta ~M~ veces algunas de las bombillas con alguno de los K colores disponibles, ellos y solo ellos conocen las razones de este proceso. Y, todo lo que necesitan para la liberación del producto perfecto, es tu ayuda con un programa que compute la belleza después de repintado cada bombillo en el proceso descrito anteriormente. Tu programa recibirá la descripción del prototipo y la secuencia de repintados.

Entrada

La primera línea contiene tres enteros ~N, M~ y ~K~ ~(2 \leq N \leq 300000, 1 \leq M \leq 300000, 1 \leq K \leq 1000 000 000)~, el número de bombillas en el prototipo de guirnalda, el número de repintados aplicados y el número de colores diferentes disponibles respectivamente.

La segunda línea contiene ~N~ enteros positivos ~C[i] (1 <= C[i] <= K)~ los colores de las ~N~ bombillas en el orden que fueron añadidas a la guirnalda.

La tercera línea contiene \(N–2\) enteros positivos ~P[j] (1 <= P[j] <= j + 1)~ el número de la bombilla que fue conectada a la bombilla ~(j+2)~-ésima. Las siguientes ~M~ líneas contienen dos enteros ~(1 \leq X \leq N, 1 \leq Y \leq K)~, el número de bombilla a repintar y el color aplicado a la misma respectivamente.

Salida

La salida debe consistir de ~M~ líneas, la i-ésima línea de la salida debe contener el número de pares de bombillas del mismo color que están conectadas por un cable después de el repintado i-ésimo.

Ejemplo # 1 de Entrada

3 3 3
1 2 3
2
2 1
3 1
2 2

Ejemplo # 1 de Salida

1
2
0

Ejemplo # 2 de Entrada

7 1 4
2 1 2 4 4 1 2
1 1 2 1 2
2 2

Ejemplo # 2 de Salida

3