블랙 가문의 가계도

타임터너는 과거로 돌아가 그곳에서 시간을 보낸 뒤 현재로 돌아올 수 있게 해 주는 마법 장치다.

로즈 그레인저는 호그와트 도서관에서 타임터너를 발견하고, 머글(마법 능력이 없는 인간)의 목숨을 구하기 위해 과거로 돌아가 블랙 가문의 일부 구성원을 제거하기로 마음먹었다.

블랙 가문에는 n명의 구성원이 있으며, 태어난 순서대로 1번부터 n번까지 번호가 붙어 있다. 1번 구성원은 기록에 남아 있는 블랙 가문의 첫 번째 구성원이다. 각 i (2 ⩽ i ⩽ n)에 대해 i번 구성원은 pi번 구성원의 직계 후손이다 (1 ⩽ pi < i). 즉, pi번 구성원과 그의 모든 조상은 i번 구성원의 조상이다. 또한 기록에 따르면 블랙 가문의 i번째 구성원은 머글 ci명의 죽음에 책임이 있다.

이제 로즈에게는 q개의 선택지가 있다. j번째 선택지는 타임터너를 사용해 과거로 돌아가 aj번부터 bj번까지의 구성원을 모두 제거한 뒤 현재로 돌아오는 것이다 (aj ⩽ bj). 이 행동의 결과로, 블랙 가문 구성원 중 aj번부터 bj번까지의 구성원을 조상으로 둔 구성원은 태어나지 않게 된다. aj번부터 bj번까지의 구성원인 i (즉, aj ⩽ i ⩽ bj)이거나 aj번부터 bj번까지의 구성원을 조상으로 둔 구성원 i에 대해, 로즈는 ci명의 목숨을 구하게 된다.

각 선택지마다 로즈가 그 선택지를 택했을 때 구하게 되는 목숨의 수를 구하라.

입력의 첫째 줄에는 두 정수 n과 q가 주어진다 (2 ⩽ n ⩽ 105, 1 ⩽ q ⩽ 105). 둘째 줄에는 n개의 정수 c1부터 cn까지가 공백으로 구분되어 주어진다 (0 ⩽ ci ⩽ 104). 셋째 줄에는 n−1개의 정수 p2부터 pn까지가 주어진다 (1 ⩽ pi < i). 다음 q개의 줄에는 각각 하나의 선택지가 주어진다. j번째 줄에는 두 정수 aj와 bj가 주어진다 (1 ⩽ aj ⩽ bj ⩽ n).

각 j (1 ⩽ j ⩽ q)에 대해, 로즈가 j번째 선택지를 택했을 때 구하게 되는 목숨의 수를 출력한다.