다리를 끊는 야만인

섬 $n$개로 이루어진 나라가 있다. 섬은 다리 $n - 1$개로 이어져 있고, 어떤 두 섬 사이에도 같은 섬을 두 번 지나지 않고 오가는 길이 정확히 하나뿐이다.

야만인이 이 나라를 공격했다. 다리가 약점이라는 것을 알아챈 야만인은 다리를 하나씩 차례로 끊는다. 섬 $i$에 사는 사람의 처음 분노는 $a_i$이다.

다리 하나가 끊어질 때 분노는 이렇게 바뀐다. 섬 $x$를 보자. 다리가 끊어지기 전에 섬 $x$의 사람이 갈 수 있는 섬의 수를 $a$, 끊어진 뒤에 갈 수 있는 섬의 수를 $b$라고 하자. 두 값 모두 섬 $x$ 자신을 포함한다. 그러면 섬 $x$의 분노에 $a - b + 1$을 곱한다.

질문은 $n - 1$개 들어온다. 각 질문은 정수 두 개 $u$와 $v$로 이루어진다. 직전 질문의 답을 $res$라고 하면, 이 질문이 끊는 다리는 섬 $u + res$와 섬 $v + res$를 잇는 다리다. 첫 질문에서는 $res = 0$으로 본다.

그 다리를 끊은 뒤 섬 $i$의 분노를 $b_i$라고 하자. $(b_1 + b_2 + \cdots + b_n)$을 $10^9 + 7$로 나눈 나머지를 새로운 $res$로 정하고, 그 값을 출력한다.

첫 번째 예제로 질문 형식을 확인해 보자. 섬이 5개이고 처음 분노는 1 2 3 4 5이다. 첫 질문은 $res = 0$이므로 섬 3과 섬 1을 잇는 다리를 끊는다. 섬 1과 섬 2의 분노에는 4가 곱해지고 나머지 세 섬의 분노에는 3이 곱해져서 분노는 4 8 9 12 15가 된다. 합이 48이므로 $res$는 48이 되고 48을 출력한다. 다음 질문에 $-47$과 $-46$이 들어오면 실제로 끊는 다리는 섬 $(-47) + 48 = 1$과 섬 $(-46) + 48 = 2$를 잇는 다리다.

첫 줄에 섬의 수 $n$이 주어진다. ($2 \le n \le 2 \times 10^5$)

둘째 줄에 처음 분노를 나타내는 정수 $n$개 $a_1, a_2, \ldots, a_n$이 주어진다. ($1 \le a_i \le 10^9 + 6$)

다음 $n - 1$개 줄에 다리를 나타내는 정수 두 개 $u_i$, $v_i$가 주어진다. ($1 \le u_i, v_i \le n$) 어떤 두 섬 사이에도 오가는 길이 정확히 하나뿐임이 보장된다.

다음 $n - 1$개 줄에 질문이 문제에서 설명한 형식으로 하나씩 주어진다. 질문이 가리키는 다리는 항상 존재하고 아직 끊어지지 않았음이 보장되며, 그 다리의 두 끝 섬 번호는 모두 1 이상 $n$ 이하다.

질문마다 $res$ 값을 질문이 들어온 순서대로 한 줄에 하나씩 출력한다.