The original title of this problem is "Tree Product Metric Voronoi Diagram Query Without One Point".
You are given two weighted trees of size , where each vertex are labeled with numbers . Let be the total weight of the shortest path from node to in tree , and define similarly.
Consider a point set of size . Similar to Manhattan metric (in fact, this is a generalization of it), we can define the distance between two points : It is the sum of two distances, . For each , please determine the "closest point" from the point . Formally, for each , you should find .
输入格式
In the first line, a single integer denoting the number of vertices in both trees is given. ()
In the next lines, description of the first tree is given. Each of the lines contains three integers , which indicates there is an edge connecting two vertices with weight ()
In the next lines, description of the second tree is given in the same format.
输出格式
Print lines containing a single integer. In the -th line, you should print a single integer denoting the answer for the point .
