개미 군락

개미들은 자신들이 지은 크고 웅장한 군락을 무척 자랑스러워한다. 그런데 군락이 너무 커진 나머지, 많은 개미들이 군락의 여러 구역 사이를 어떻게 오가야 하는지 몰라 곤란을 겪고 있다. 개미들에게는 당신의 도움이 절실하다.

이 군락은 터널로 연결된 $N$개의 개미집으로 이루어져 있다. 개미들은 꼼꼼한 성격이라 개미집을 지은 순서대로 번호를 매겼다. 가장 먼저 지은 $0$번 개미집은 터널이 필요 없었다. 그 뒤에 지은 $1$번부터 $N-1$번까지의 각 개미집에 대해서는, 새 개미집을 이미 지어져 있던 개미집 중 하나와 잇는 터널을 정확히 하나씩 팠다. 이 터널 하나만으로도 어떤 개미든(필요하면 다른 개미집을 거쳐서) 그 전에 지은 모든 개미집으로 갈 수 있었기 때문에, 개미들은 더는 터널을 파지 않고 계속 개미집만 지어 나갔다.

군락의 구조와 여러 개의 질의가 주어진다. 각 질의마다 주어진 두 개미집 사이의 최단 경로의 길이를 구하라. 경로의 길이는 지나가는 모든 터널의 길이의 합이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 여러 줄에 걸쳐 주어진다.

첫째 줄에는 군락의 개미집 개수를 나타내는 정수 $N$이 주어진다 ($2 \le N \le 10^5$).

이어지는 $N-1$개의 줄은 각각 터널 하나를 나타낸다. $1 \le i \le N-1$에 대해 $i$번째 줄에는 두 정수 $A_i$와 $L_i$가 주어지며, 이는 $i$번 개미집이 길이 $L_i$인 터널로 $A_i$번 개미집과 직접 연결되어 있음을 뜻한다 ($0 \le A_i \le i-1$, $1 \le L_i \le 10^9$).

그다음 줄에는 질의의 개수를 나타내는 정수 $Q$가 주어진다 ($1 \le Q \le 10^5$). 이어지는 $Q$개의 줄에는 각각 서로 다른 두 정수 $S$와 $T$가 주어지며 ($0 \le S, T \le N-1$), 이는 한 질의의 출발 개미집과 도착 개미집을 나타낸다.

마지막 테스트 케이스 뒤에는 $0$ 하나만 적힌 줄이 온다.

각 테스트 케이스마다 $Q$개의 정수를 한 줄에 출력한다. 각 정수는 해당 질의의 두 개미집 사이의 최단 경로의 길이이며, 질의가 입력에 주어진 순서와 같은 순서로 출력한다.