정화조

경곽에는 아주 거대한 정화조 시설이 있다. 정화조의 구조는 다음과 같다. 먼저 원천(source)에서 여러 개의 펌프로 물을 퍼 올린다. 물은 수도관을 따라 여러 정화조를 거친다. 수도관은 정화조와 다른 정화조를 잇는다. 수도관은 트리 형태의 간선 구조이다. 즉, 수도관을 따라 물이 이동할 때 한 정화조를 두 번 이상 지나지 않으며, 펌프에서 퍼 올린 물은 모두 최종적으로 한 정화조에 모인다. 위 그림에서 동그라미는 정화조를, 화살표는 수도관을 나타낸다. 펌프에서 퍼 올린 물은 처음으로 트리의 리프에 있는 정화조로 이동한다. (리프는 자기에게로 향하는 수도관이 없는 정화조를 뜻한다.) 물은 수질에 따라 여러 등급으로 나뉜다. 가장 깨끗한 물은 0등급이고, 1등급, 2등급, 3등급, $\ldots$ 순으로 물이 더러워진다. 처음에 원천의 물은 0등급이다. 물이 수도관을 따라 한 정화조에서 다른 정화조로 이동할 때마다 물은 오염되어 수질이 한 등급 올라간다. 정화조에 처음 도착한 물의 수질도 1등급으로 본다. 물이 정화조를 지날 때, 정화조는 이 물을 정화할 수도 있고, 그대로 흘려보낼 수도 있다. 정화조에는 고유 비용 $c_i$가 있다. 정화조에서 물을 정화하면 $c_i \times$ (정화할 물의 수질 등급) 만큼의 비용이 든다. 정화된 물은 0등급이 된다. 물을 정화하지 않으면 비용이 들지 않고 물의 수질도 변하지 않는다. 정화조마다 두 수 $l_i$, $r_i$ ($l_i \leq r_i$)가 주어진다. $i$번째 정화조는 수질 등급이 $l_i$ 이상 $r_i$ 이하인 물만 정화할 수 있다. 경곽은 막대한 정화조 공사를 위해 일시적으로 정화조의 운영을 중단하려고 한다. 정화조의 운영을 중단한다는 것은 물이 그 정화조를 지나갈 수 없게 만든다는 뜻이다. 다만 경곽으로의 물 공급이 끊기면 안 되기 때문에, 몇 개의 정화조는 계속 운영한다. 경곽에게는 쿼리가 주어진다. 각 쿼리에는 정화조 번호 $X$와 수질 $K$가 주어진다. 경곽은 원천과 정화조 $X$를 잇는 경로 하나를 제외한 나머지 정화조를 모두 중단하려고 한다. 이때 $X$에서 $K$등급 이하의 물을 얻으려면 최소 몇의 비용이 필요한지 구해야 한다. 경곽의 문제를 함께 해결해 주자. 쿼리는 서로 독립적이다. 즉, 한 쿼리에서 중단한 정화조가 다음 쿼리에서도 무조건 중단되는 것은 아니다.

첫 번째 줄에 정화조의 개수 $N$이 주어진다. 두 번째 줄에 $N$개의 정수 $c_1, c_2, \ldots, c_N$이 주어지며, $c_i$는 $i$번째 정화조의 고유 비용이다. 다음 $N$개의 줄에 $l_i$와 $r_i$($l_i \leq r_i$)가 주어진다. 다음 $N-1$개의 줄에 수도관 정보 $u_i$, $v_i$가 주어진다. 이는 $u_i$번째 정화조에서 $v_i$번째 정화조로 수도관이 이어져 있다는 뜻이다. 다음 줄에 쿼리의 개수 $Q$가 주어진다. 다음 $Q$개의 줄에 $X_i$와 $K_i$가 주어진다. 이는 원천과 정화조 $X_i$를 잇는 한 경로에서 $K_i$ 이하의 수질 등급을 얻는 데 필요한 최소 비용을 구하라는 뜻이다.

$Q$개의 줄에 각 쿼리의 답을 한 줄에 하나씩 출력한다. $K_i$ 이하의 수질 등급 물을 얻을 수 없으면 -1을 출력한다.

값의 범위는 다음과 같다. $1 \leq N, Q \leq 250,000$, $1 \leq c_i \leq 100,000,000$ ($1 \leq i \leq N$), $0 \leq l_i \leq r_i \leq N$ ($1 \leq i \leq N$), $1 \leq u_i, v_i \leq N$, $u_i \neq v_i$ ($1 \leq i \leq N-1$), $1 \leq X_i \leq N$ ($1 \leq i \leq Q$), $0 \leq K_i \leq N$ ($1 \leq i \leq Q$).