Alice is a merchant in the world. Layout of this world is a tree on N nodes (i.e., there is only one simple path between any two cities). Each city has an infinite number of gems, each with cost Ti dollars and brightness Si. Suppose Alice traveled from city U to city V on the shortest path and started with K dollars, then the maximum total brightness (from gems purchased on her route, without exceeding K dollars) she can achieve is a some function; let’s call it f(K). Compute the following 2 quantities: ∑k i=1 Input A number of inputs (≤ 20) described as follows. Input start with N, the number of cities (0 < N ≤ 40000) and K (0 < K ≤ 61), the maximum dollars. This is followed by N − 1 line consecutively, with two numbers x and y between 1 and N on each line, specifying there is a road between cities x and y. Next is a line with N numbers, which is the cost of the gems Ti (0 < Ti ≤ K). This is followed by a line with N integers, the brightness of the gems Si (0 < Si ≤ 106), The next line is an integer Q, the number of inquiries (0 < Q ≤ 40000). Then Q lines, each line input two positive integer U , V , which meansAlicetravelsfromcityU tocityV. Notethat1≤x,y,U,V ≤N. Output Output for each query, g(K) and h(K), separated by a space. Sample Input 5 10 12 23 24 15 12345 10 15 30 45 50 2 11 54 Sample Output 550 14 600 64 g(K)= f(i)andh(K)=f(1)∧f(2)···∧f(K)where ∧ meansXOR.