계층 구조

Andi는 ACM(Association for Cool Magics)에서 일한다. 이 회사는 인터넷에 재미있는 콘텐츠, 예를 들어 밈, 농담, 게임 등을 만드는 일을 한다. ACM의 근무 환경은 즐겁고 모든 직원이 동등하게 대우받지만, 회사가 원활하게 돌아가려면 전체 직원의 계층 구조가 필요하다.

ACM에는 N명의 직원이 있고 각자 1부터 N까지의 고유한 ID를 가진다. 한 명(보통 ACM에서 “big boss”라고 부르는 사람)을 제외한 모든 직원은 직속 상사를 정확히 한 명씩 가진다. big boss에게는 상사가 없으므로 이 계층 구조는 big boss를 루트로 하는 트리(그래프 이론에서의 트리)와 같으며, big boss가 모든 직원 중 가장 높은 직급이다.

ACM은 직원에게 프로젝트를 배정하는 방식이 독특하다. 어떤 프로젝트가 두 직원 a와 b에게 배정되었다면, 계층 구조 트리에서 a와 b 사이의 경로에 있는 모든 직원도 이 프로젝트에 참여한다. a와 b를 포함한 이 직원들을 프로젝트의 구성원이라고 한다. 다른 회사에서는 보통 가장 높은 직급의 구성원이 논의를 이끌지만 ACM은 다르다. ACM은 재미있고 창의적인 아이디어를 만드는 데 집중하므로, 논의는 도중에 나오는 어떤 농담이든 이해할 수 있는 사람이 이끌어야 한다. 그래서 구성원들은 나이가 l 이상 r 이하인 사람이 논의를 이끌기로 합의한다. Andi는 논의를 이끌 수 있는 직원들의 나이 합이 얼마인지 궁금해한다. 논의를 이끌 수 있는 직원이 아무도 없을 수도 있으며, 이때 합은 0이다.

ACM의 계층 구조와 Q개의 질의가 주어진다. 각 질의는 a, b, l, r로 이루어지며, a와 b는 프로젝트가 배정된 두 직원이고 l과 r은 나이 범위이다. 각 질의마다 프로젝트에 참여한 직원 중 나이가 l 이상 r 이하인 직원들의 나이 합을 구하라.

입력은 두 정수 N Q (1 ≤ N ≤ 100000; 1 ≤ Q ≤ 100000)로 시작한다. N은 직원 수, Q는 질의 수이다. 다음 줄에는 N개의 정수 Ai (1 ≤ Ai ≤ 109)가 주어지며, Ai는 i번째 직원의 나이이다. 다음 N-1개 줄에는 각각 두 정수 x y (1 ≤ x, y ≤ N; x ≠ y)가 주어지며, x가 y의 직속 상사임을 나타낸다. 각 직원은 직속 상사를 최대 한 명 가진다. 다음 Q개 줄에는 각각 네 정수 a b l r (1 ≤ a, b ≤ N; 0 ≤ l ≤ r ≤ 109)이 주어지며, 이 질의에 답해야 한다.

각 질의마다 프로젝트에 참여한 직원 중 나이가 l 이상 r 이하인 직원들의 나이 합을 한 줄에 출력한다.