"The difficulty of the road to Shu, harder than ascending to heaven..."

Reciting the newly learned Chinese text, A and B walked out of the north school gate. It had been a long time since the 7:00 PM dismissal, yet it was still some time before the crowd would emerge after the 10:45 PM evening self-study session. The pedestrians in the alley were sparse.

"The exam is tomorrow morning," A said in a low, stiff voice.

"Hmm... reciting such a text, there really is a sense of the dashing spirit of the literati," B replied.

"Hey, enough. Have we learned any 'literature'? We spend every day in the computer lab typing code and grinding problems; when we feel inspired by the scenery, we only have a couple of lines of poetry learned in Chinese class to get by."

"Don't expose the hardships of life... Tell me, did the ancient Shu people three thousand years ago really rely on 'heavenly ladders and stone plank roads connected' to travel?"

"They lived in the Sichuan Basin, the land of abundance, okay? Those living in the mountains were the Miao-Man, tribal people of the wilderness; why would they climb mountains and walk on plank roads every day? Plank roads were built on a large scale only hundreds of years later, when the Qin State managed the Shu region."

"Then the people in front, were they like those on the Loess Plateau, relying on shouting to communicate?"

"Perhaps they heard the sounds of chickens and dogs, lived and died without visiting each other, and didn't need to communicate like that at all."

"Compared to that, I would rather believe they truly had heroes like those in 'the earth collapses and the mountains crumble, the brave men die'."

"Things from thousands of years ago, who can say for sure."

"You can't say that... I prefer to believe that information is conserved, and everything in history leaves a trace."

"Then you should be an archaeologist."

"But you know about chaos, right?"

Temporarily speechless, A stopped the two of them under that locust tree.

Suddenly, he recited with clear articulation and precise rhythm:

"Above are the high peaks where six dragons turn back the sun—below are the swirling rivers that rush and reverse. The flight of the yellow crane—still cannot pass, the apes and monkeys want to cross, worrying about where to climb."

"How winding is the Green Mud Ridge, with a hundred steps and nine turns winding around the rocky peaks. Touching the stars and passing the wells, I look up and hold my breath, stroking my chest with my hand and sitting down to sigh." B, who was staring blankly at the tree trunk, also echoed in a low voice.

Then, as always, that girl appeared from behind the tree trunk, still in white, wearing a flower crown, smiling gently, saying nothing. A still lowered his head slightly to play with the corner of his clothes, and B smiled as usual.

She stroked their heads, and A and B did not call the police. A trance flashed by.

Facing the high peaks and deep valleys, the continuous mountains and sheer cliffs before him, A could not help but recall Li Daoyuan's words learned in junior high: "The layered rocks and stacked peaks hide the sky and block the sun; unless it is noon or midnight, the sun and moon cannot be seen." The remark he had just used to mock B, about regretting not having read enough books when the time came to use them, instead seeped into his own heart. The stone chambers by the water in the distance were faintly visible, as if there were signs of human habitation; the silhouettes of houses appeared on the mountaintops.

Suddenly, his hand was held by B. A, intoxicated by the cries of apes and the singing of birds, suddenly realized that he was in a dream brought by LCR.

"This seems to be the content of 'The Road to Shu' we were just discussing."

A also realized it, but he did not see any sign of a plank road. It seems these were the "Miao-Man" from even earlier than the King of Qin.

"Then let's observe the problem we just discussed. How do people without plank roads communicate?"

The most direct method would be to climb vines and cross mountains, which is an inherent skill of the ancestors who lived off the mountains—but proficiency in the craft cannot offset the dangers of snakes, insects, and falling in the mountains. Passing information this way is not worth the loss. B believed there must be a more professional method.

The valley gradually brightened, and A, with his sharp eyes, noticed something unusual about the mountain wall covered by trees. The two climbed up to it; thanks to it being a dream, they didn't expend much effort. It turned out that a split bamboo tube, about a foot wide and fixed with small bamboo strips, stretched along the mountain. Spring water flowed through it; it was likely a facility for the mountain people to divert water.

"That's not right. The people down the mountain have river water in the valley to take. Moreover, to transport water, they should use complete, not split, pipes."

Then, a small bamboo tube tied with a rope slid past them in the trough where the spring water was flowing.

"This is..."

"That's it! This small tube is a tool for the people on the mountain and below to exchange small items—including information carriers. The flowing water is to clear away silt. The split, rather than closed, bamboo tube is also to prevent jamming."

"But wouldn't the small tube easily slide out of a trough that is only half a tube?"

"Observe carefully, the small tube has a two-section structure, which allows it to receive water while storing information. The spring water also acts as a guide. And the rope on top can also be retrieved—this means communication is two-way, although the initiator is always at a higher place, but one only needs to wait to solve the problem in the opposite direction."

"That's probably it, but this is a world brought by LCR. I don't know if our ancestors really did this in the Qinba Mountains."

"If there is a stable spring, this should be feasible."

"Such creativity," B said, "shows that our ancestors understood technology better than science."

Then he suddenly fell silent. "Is that really the case?"

Then the two began to float—a reminder of the reality that they were in a dream.

A noticed that near this mountain, there were many such "channels" for transmitting objects with flowing water, and they formed a large tree-like network.

"They not only invented such a method, but also made a wise plan that conforms to scientific principles."

"Look. They connected all the settlements with the route of the fewest segments, the heights of all their settlements were in an arithmetic progression when sorted, any two of their settlements could communicate with each other by passing through at most one other settlement, and the height difference of the pipes was the most economical."

I wonder who is speaking.

...

A thought for a while and said:

"In other words, although the location of the settlements could not be moved due to natural conditions, they made the wisest choice in the pipe connection scheme."

B replied:

"Yes. What LCR meant just now, described in terms of the OI we learned, is probably like this: pipes can be seen as edges between two settlements.

1. They connect the settlements with the minimum cost, that is, they form a tree;
2. The pipes at the same settlement are interconnected and managed by someone, which means that as long as the height direction of the pipes between two settlements is monotonic—the settlement height is always increasing or always decreasing—they can communicate directly.
3. Any two settlements need at most one relay to communicate;
4. The heights of all settlements are an arithmetic progression when sorted;
5. The cost of a pipe is proportional to the height difference between the two end settlements, and the sum of the costs formed by the height differences happens to be the minimum among all possible arrangements of settlement heights;"

"But the height of the settlements is not decided by people."

"So, this point is the beauty of mathematics, the crystallization of nature's coincidence and human wisdom. There is nothing more romantic than this."

"Very good... but if a new settlement is added, things will be ruined."

"Fortunately, this is a dream world. We might be able to play the savior and change the height of the settlements."

"Then how should we do it?"

"First is abstraction. We treat the settlements as a tree with $n$ nodes, the nodes of the tree are labeled from $1$ to $n$, and the weight of an edge is the absolute difference between the labels of the two endpoints. The weight of the entire tree is the sum of all edge weights. In addition, the tree must satisfy a condition: for any two points, either the labels on the path between them (including the endpoints) are monotonic (increasing or decreasing), or there exists a third point that satisfies this condition with both of these two points.

Then our task is to find, for a given tree structure, the minimum weight of the entire tree that can be obtained by changing the node labeling method under these premises.

And, we also need to maintain this after adding new leaves."

...

The eleven o'clock bell was about to ring, and students passed by the locust tree one after another. No one could notice the sleepwalking of the two students who had been sleeping soundly under the tree two hours ago.

Please complete B's vision.

Description

For a labeled rooted tree $T=(V,E)$, a labeling $p:v\rightarrow p(v),v\in V,p(v)\in [1,|V|]\cap \mathbb{Z}$ is a bijection. Let the weight of an edge $e = (u,v),e\in E$ be: $w:e\rightarrow w(e) = \lvert p(u)-p(v) \rvert,e\in E,w(e)\in \mathbb{Z}$. Let the weight of the entire tree be: $W:T=(V,E)\rightarrow W(T)=\sum_{e\in E}w(e)$.

Additionally, define a graph $G(T)=(V,E')$, where $(u,v)\in E'$ if and only if the labels $p_1,p_2,\cdots , p_l$ of the points on the path from $u$ to $v$ in $T$ are either monotonically increasing or monotonically decreasing. Then $p$ must ensure that the diameter of $G(T)$ does not exceed $2$, i.e., $\mathop{\max}_{i,j\in V}SP(i,j)\le 2$, where $SP(i,j)$ denotes the number of edges in the shortest path between $i$ and $j$ in $G(T)$.

Given $T$, find $M(T)=\mathop{\min}_{p}W(T)$.

There are several operations: add a new leaf $v$ to $T$ ($V\gets V\cup \{v\},E\gets E\cup \{(x,v)\},x\in V_{old}$), and after each operation, $M(T)$ is also required. These operations are cumulative.

Input

The first line contains a positive integer $n$ representing the initial $\lvert V\rvert$. These points will be represented by integers from $1$ to $n$ in the following format; please do not confuse them with the pending labels $p$.

The next $n-1$ lines each contain two positive integers $u_i, v_i$, representing the initial $E=\{(u_i,v_i):i=1,2,\dots ,n-1\}$, ensuring $u_i < v_i = i+1$.

The next line contains a non-negative integer $q$ representing the number of modifications.

The next $q$ lines each contain a positive integer $f_i$, representing the addition of a point (represented as $n+i$) and a new edge $(f_i,n+i)$.

Output

A total of $q+1$ lines, each containing a non-negative integer, representing $M(T)$ initially and after each modification, respectively.

Examples

Input 1

1
2
1
1

Output 1

0
1
2

Note 1

The tree is a chain each time (1, 1-2, 3-1-2). Simply set $p(i)$ equal to the number of points from $i$ to the end of the chain that was added later.

Input 2

5
1 2
2 3
3 4
4 5
5
4
6
1
1
7

Output 2

4
6
7
8
10
11

Input 3

14
1 2
1 3
2 4
1 5
2 6
1 7
1 8
2 9
2 10
2 11
2 12
2 13
1 14
12
1
1
2
2
2
2
2
2
2
2
1
2

Output 3

35
41
48
53
58
64
70
77
84
92
100
108
117

Note 3

Satisfies Property 1.

Constraints

For all data, $1\le n\le 10^5, 0\le q\le 10^5, 1 \le n + q \le 10^5$.

Detailed data limits and conventions for each subtask are as follows (blank cells indicate the same as the conventions for all data above):

Property One: $\forall i,u_i,f_i\le 2$

Property Two: $\forall i,u_i,f_i\le 20$

Property Three: $\forall i,u_i$ are uniformly random in $1,2, \dots ,i-1$; $\forall i,f_i$ are uniformly random in $1,2, \dots ,n+i-1$.