Visits

Byteasar is a remarkable man. Over the last 21 years he was a postman, a banker, an ice skater, and even a king! No wonder he has many friends. Or had, since his constant changes of profession and workplace made him lose touch with many old friends. . . The time has come to change that! Bytasar is about to start a grand tour of Byteotia to renew old friendships.

There are n towns in Byteotia, connected by a network of n−1 bidirectional roads. Our protagonist wants to visit every town, and he has already fixed the order of these visits. From each town to the next on his itinerary, he drives a car rented from BMW (Byteotian Motor Wagons). Each rental is completely free, but the cars must be refueled: a car with a tank of capacity k is filled at the very beginning and then refueled after every k traversed roads. BMW knows Byteasar's plan well and knows that he intends to finish his journey as soon as possible. So they have cunningly chosen the tank capacities of their rentals so that in every town Byteasar has to (re-)fuel two cars: the one he arrives in and the one he leaves in. The initial and final towns are exceptions, where only one car has to be fueled.

Given Byteasar's itinerary, the fuel prices, and the tank capacities, determine how much each segment of the route will cost.

The first line of the standard input contains a single integer n (2 ≤ n ≤ 50 000), the number of towns in Byteotia. The towns are numbered from 1 to n. The next line contains a sequence of n integers c1, . . . , cn (1 ≤ ci ≤ 10 000), separated by single spaces, giving the fuel prices in all the towns of Byteotia: the number ci is the cost of filling the tank of any car in town no. i. This is a "buffet fueling", that is, "fill as much as you can for only ci".

The n − 1 lines that follow describe the road network of Byteotia. Each of those lines contains two integers a and b (1 ≤ a, b ≤ n), separated by a single space, meaning that a two-way road connects towns no. a and b.

After those comes a line with a sequence of n integers t1, . . . , tn, separated by single spaces, giving the order in which Byteasar is going to visit the towns (each of the numbers from 1 to n appears exactly once in this sequence). The last line of the input contains a sequence of n − 1 integers k1, . . . , kn−1, separated by single spaces, giving the tank capacities of the rental cars: the number ki means that on the ride from town no. ti to town no. ti+1, Byteasar has to refuel his car after every ki roads traversed. You may assume that ki always divides the distance between those towns.

In tests worth 36% of the total score, the condition n ≤ 10 000 holds. In a subset of those, worth 28% of the total score, a stronger condition n ≤ 1000 holds.

Your program should print n − 1 lines to the standard output, each containing a single integer. The number in the i-th line should be the total cost of refueling on the way from town no. ti to town no. ti+1.