스타블로

토니는 HONI(및 COCI)에 낼 문제를 만들기로 했다. 아이들을 좋아하지 않는 그는 문제를 최대한 어렵게 만들었다. 참가자를 괴롭히려고 끊임없이 변하는 트리에 관한 복잡한 문제를 고안했다.

가중치가 없는 트리가 루트를 정점 $1$로 하는 정점 $N$개로 주어진다. 각 정점 $i$에는 값 $v_i$가 있다. 트리의 구조는 배열 $p_i$로 주어지며, $1$부터 $N-1$까지의 각 $i$에 대해 $p_i$는 정점 $i+1$의 부모다.

정점 $y$에 대해 다음과 같이 정의한다.

$f(y) = \sum_{x \in S_y} d(x, y) \cdot v_x$

여기서 $d(x, y)$는 정점 $x$와 $y$ 사이의 거리이고, $S_y$는 $y$가 조상인 모든 정점의 집합이다.

$Q$개의 질의가 주어지며, 각 질의는 정점 $x$와 $y$로 이루어진다. 각 질의마다 트리에 다음 변환을 적용한 뒤 $f(y)$를 구한다.

1. $x$의 자식을 모두 $x$의 부모에게 붙인다.
2. $x$를 트리에서 뗀다.
3. $x$를 $y$와, $x$가 떨어져 나온 부분트리 쪽 $y$의 자손 사이에 다시 끼워 넣는다.

$y$가 $x$의 부모이면 트리는 바뀌지 않는다. 정점 $x$는 항상 $y$의 부분트리에 속한다. 변환은 임시로 적용되며, 질의가 끝나면 트리는 원래 상태로 돌아간다.

첫 줄에 두 정수 $N$과 $Q$가 주어진다 ($1 \le N, Q \le 5 \cdot 10^5$). 각각 정점의 수와 질의의 수다.

둘째 줄에는 $N$개의 정수 $v_i$ ($1 \le v_i \le 10^6$)가 주어진다. 각 정점의 값이다.

셋째 줄에는 $N-1$개의 정수 $p_i$ ($1 \le p_i \le i$)가 주어진다. $p_i$는 정점 $i+1$의 부모다.

이어지는 $Q$개의 줄에는 각각 두 정수 $x$와 $y$ ($1 \le x, y \le N$)가 주어진다.

각 질의에 대해, 변환을 적용한 트리에서의 $f(y)$ 값을 다음 $Q$개의 줄에 한 줄씩 출력한다.

위 첫 번째 테스트에 대한 설명: 변환 후 정점 $3$은 정점 $1$과 거리 $1$에 있고, 정점 $2$는 정점 $1$과 거리 $2$에 있다. 결과는 $3 + 2 \cdot 2 = 7$이다.