트리

정점이 $N$개인 트리를 생각합니다. 정점은 0번부터 $N - 1$번까지 번호가 붙어 있습니다. 0번 정점을 루트라고 합니다. 루트를 제외한 모든 정점은 부모가 정확히 하나 있습니다. $1 \le i < N$을 만족하는 각 $i$에 대해 정점 $i$의 부모는 $P[i]$이며, $P[i] < i$입니다. 또한 $P[0] = -1$로 둡니다.

임의의 정점 $i$ ($0 \le i < N$)에 대해, 정점 $i$의 서브트리는 $i$ 자신, 부모가 $i$인 정점, 조부모가 $i$인 정점, 증조부모가 $i$인 정점 등을 모두 포함하는 정점의 집합입니다.

아래 그림은 정점이 $N = 6$개인 트리의 예입니다. 루트를 제외한 각 화살표는 정점에서 부모를 가리킵니다. 정점 2의 서브트리는 정점 2, 3, 4, 5를 포함합니다. 정점 0의 서브트리는 6개 정점 전부를 포함하고, 정점 4의 서브트리는 정점 4만 포함합니다.

각 정점에는 음이 아닌 정수 가중치가 주어집니다. 정점 $i$의 가중치는 $W[i]$로 나타냅니다.

$Q$개의 질의에 답하는 프로그램을 작성해야 합니다. 각 질의는 양의 정수 쌍 $(L, R)$로 주어지며, 답은 다음과 같이 계산합니다.

각 정점에 정수인 계수를 하나씩 배정합니다. 이 배정은 수열 $C[0], \dots, C[N-1]$로 나타내며, $C[i]$는 정점 $i$의 계수입니다. 이 수열을 계수 수열이라고 합니다. 계수는 음수, 0, 양수 중 무엇이든 될 수 있습니다.

질의 $(L, R)$에 대해, 모든 정점 $i$ ($0 \le i < N$)에서 정점 $i$의 서브트리에 속한 정점들의 계수 합이 $L$ 이상 $R$ 이하이면, 그 계수 수열을 유효하다고 합니다.

계수 수열에서 정점 $i$의 비용은 $|C[i]| \times W[i]$입니다. 전체 비용은 모든 정점의 비용을 더한 값입니다. 각 질의에 대해 유효한 계수 수열 중 전체 비용의 최솟값을 구하세요.

어떤 질의에 대해서도 유효한 계수 수열이 적어도 하나 존재함이 증명되어 있습니다.

• $1 \le N \le 200000$
• $1 \le Q \le 100000$
• $P[0] = -1$
• $1 \le i < N$인 각 $i$에 대해 $0 \le P[i] < i$
• $0 \le i < N$인 각 $i$에 대해 $0 \le W[i] \le 1000000$
• 각 질의에서 $1 \le L \le R \le 1000000$