# KOI 22 Outer Ring Road

https://www.acmicpc.net/problem/25407

KOI city consists of $N$ intersections and $N-1$ bidirectional roads, allowing travel between any two intersections using roads alone. Each road has a non-negative integer weight representing the time it takes to travel on that road.

The intersections are assigned ranging from $1$ to $N$. The numbering system satisfies the following properties:

* Intersection $1$ is the city center and is guaranteed to be adjacent to at least two roads.
* The numbering of intersections follows a preorder traversal of the tree rooted at intersection $1$.
* For every intersection, consider the adjacent intersections (directly connected by a road) with the smallest number. When listing these intersections in counterclockwise order, the numbers increase.

As KOI city grew, traffic congestion worsened. To alleviate this, the mayor connected the outermost intersections with a outer ring road. Let's denote the intersections connected by a single road in increasing order as the list ${v_1, v_2, \dots , v_k}$. The mayor constructed bidirectional roads connecting each $v_i$ with $v_{(i \pmod k)+1}$. The weight of each new road is a non-negative integer $w_i$, provided as input.

You are tasked with building a navigation system for KOI city. The system should efficiently respond to $Q$ queries $u, v$ asking for the minimum time required to travel from intersection $u$ to intersection $v$. The minimum time is the smallest sum of the weights of the roads along any path between $u$ and $v$.

Given the road network and the queries, write a program to efficiently answer these $Q$ queries.

## Input

The first line contains the number of intersections in KOI city, $N$.

The next $N-1$ lines each contain two integers $p_i$ and $c_i$, representing a bidirectional road of weight $c_i$ between intersection $p_i$ and intersection $i+1$.

Before the construction of the peripheral road, $k$ is the number of intersections connected by a single road, and the list ${v_1, v_2, \dots , v_k}$ is given in increasing order. The next line contains $k$ integers $w_1, w_2, \dots , w_k$, representing the weights of the peripheral roads connecting $v_i$ with $v_{(i \pmod k)+1}$.

The following line contains the number of queries, $Q$.

The next $Q$ lines each contain two integers $u$ and $v$, the intersections for which the minimum travel time is to be found.

## Output

For each of the $Q$ queries, output a single integer representing the minimum travel time between intersections $u$ and $v$.

## Constraints

* $4 \leq N \leq 100,000$
* $1 \leq p_i \leq i$
* $0 \leq c_i, w_i \leq 10^{12}$
* $1 \leq Q \leq 250,000$
* $1 \leq u, v \leq N$, $u \ne v$

## Subtasks

1. (6 points) For all queries, $u = 1$.
1. (8 points) For all $1 \leq i \leq N-1$, $p_i = 1$.
1. (5 points) For all $1 \leq i \leq N-1$, $c_i \leq 10^6$ and for all $1 \leq i \leq k$, $w_i = 10^{12}$.
1. (15 points) For all $1 \leq i \leq k$, $w_i = 0$.
1. (57 points) No intersection is connected to more than 4 roads.
1. (9 points) No additional constraints.

## Examples

### Example Input 1

4
1 9
1 8
1 0
9 9 9
6
1 2
1 3
1 4
2 3
2 4
3 4

### Example Output 1

9
8
0
9
9
8


### Example Input 2

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
0 0 0 0 0 0
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

### Example Output 2

7
8
8
7
7
7
0
7
1
7
7
7
1
7
0
7
0
8
1
6
0

### Example Input 3

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

### Example Output 3

9
8
8
15
9
14
0
7
1
7
14
9
15
9
22
9
23
8
15
16
16

The map above corresponds to Examples 2 and 3. In Example 2, it satisfies $w_i = 0$, and in Example 3, it satisfies $w_i = 10^{12}$. Example 2 satisfies the conditions of subproblems 4, 5, and 6, while Example 3 satisfies the conditions of subproblems 3, 5, and 6.