Ants Colony

A colony of ants is proud of the magnificent, sprawling home they have built. But its sheer size has become a problem: many ants do not know how to travel between different parts of the colony. They urgently need your help.

The colony consists of $N$ anthills connected by tunnels. Being meticulous, the ants numbered the anthills in the order they were built. The first anthill, numbered $0$, needed no tunnel. For each later anthill, numbered $1$ through $N-1$, the ants dug exactly one tunnel connecting the new anthill to one of the anthills that already existed. That single tunnel was always enough to let an ant reach any previously built anthill (possibly by passing through others), so the ants never dug extra tunnels and simply kept building.

Given the structure of the colony and a list of queries, compute for each query the length of the shortest path between the two given anthills. The length of a path is the sum of the lengths of all tunnels traveled.

The input consists of several test cases. Each test case is given over several lines.

The first line contains an integer $N$, the number of anthills in the colony ($2 \le N \le 10^5$).

Each of the next $N-1$ lines describes one tunnel. For $1 \le i \le N-1$, line $i$ contains two integers $A_i$ and $L_i$, meaning that anthill $i$ is connected directly to anthill $A_i$ by a tunnel of length $L_i$ ($0 \le A_i \le i-1$ and $1 \le L_i \le 10^9$).

The next line contains an integer $Q$, the number of queries ($1 \le Q \le 10^5$). Each of the next $Q$ lines contains two distinct integers $S$ and $T$ ($0 \le S, T \le N-1$), the source and target anthills of one query.

The last test case is followed by a line containing a single $0$.

For each test case, output a single line with $Q$ integers: the length of a shortest path between the anthills of each query, in the same order as the queries appear in the input.