Going to movie

Chip'n'Dale are helping everyone on the country iLandia. One upon time after successful ending of their missions they decided to go to the cinema. But the trouble. There is only one cinema in ILandia, which is situated in capital. Chip eds his adventure in city $x$ and Dale in city $y$. There is a lack of time till the begin of film session, that is why both of them have decided to order a taxi. Unfortunately our heroes doesn't earn a lot of money from their work. Both of them want to spend as small as possible. Chip can share the cab with Dale and Dale can do the same, but they need to be in one city. In order to that all taxi drivers in iLandia have the same fixed rate for one km. That means that they will split cost for the way which they spend together. You have few scenario of ending adventure of Chip'n'Dale in a different cities. You need to calculate minimum sum of money which they need to get to cinema (for each scenatio).

There is only one road between two city. The distance between two neighboring cities is $1$ km. The capital always have number $1$.

Input

The first line contains two positive integers: the number of cities $n(1\le n\le 10^5)$ in iLindia and the rate $Price(1\le Price\le 10^4)$ in cab per $1$ km. In the next $n-1$ lines two positive integers $x$ and $y(1\le x,y\le n)$ are given, they describe the road between city $x$ and city $y$. All roads are two-way. The next line contains the number of scenarios $q(1\le q\le 10^5)$. Each scenario starts with city numbers $c$ and $d(1\le c,d\le n)$ where Chip'n'Dale will finish their adventures.

Output

Print two numbers — the amount of money spent by Chip and Dale, with precision no less than $10^{-5}$.

Examples