Поход в кино

Чип и Дейл помогают всем в стране iLandia. Как-то после удачного завершения своих миссий они решили сходить в кино. Но тут их поджидала неожиданность! В стране есть только $1$ кинотеатр, который находится в столице. Чип завершил свои приключения в городе $x$, а Дейл в городе $y$. До начала сеанса осталось мало времени, поэтому оба решили заказать такси, чтобы успеть к началу сеанса. Так как гонорары наших героев небольшие, то каждый желает потратить на такси как можно меньше денег. Чип может подсесть в такси к Дейлу и наоборот, если они оказались в одном городе. Так как у таксистов iLandии постоянная такса за километр, то затраты на путь, который они проехали вдвоем, делят на $2$. Вам задано несколько сценариев завершения приключений Чипа и Дейла в разных городах. Для каждого сценария нужно посчитать минимальные вознаграждения героев, чтобы они смогли попасть в кино.

Между двумя произвольными городами существует только одна дорога, по которой между ними можно проехать. Расстояние между любыми двумя соседними городами (между которыми существует прямая дорога) составляет $1$ километр. Столица всегда имеет номер $1$.

Входные данные

В первой строке находится два натуральных числа: количество городов $n(1\le n\le 10^5)$ в iLandia, и цена $Price(1\le Price\le 10^4)$ за $1$ км в стране. Каждая из следующих $n-1$ строк содержит два натуральных числа $x$ и $y(1\le x,y\le n)$, описывающих наличие дороги из города $x$ в город $y$. Все дороги двухсторонние. В следующей строке задается количество сценариев $q(1\le q\le 10^5)$. Каждый сценарий начинается с новой строки и задаётся номерами городов $c$ и $d(1\le c,d\le n)$, в которых заканчивают свои приключения соответственно Чип и Дейл.

Выходные данные

Выведите два числа: затраты Чипа и Дейла на дорогу с точностью не менее $10^{-5}$.

Примеры