Похід в кіно

Чіп і Дейл допомагають усім у країні iLandia. Якось після успішного завершення своїх місій вони вирішили піти в кіно. Але біда! У країні є лише $1$ кінотеатр, який знаходиться у столиці. Чіп закінчив свої пригоди у місті $x$, а Дейл у місті $y$. До сеансу залишилося обмаль часу, тому обоє вирішили замовити таксі, щоб встигнути на початок сеансу. Оскільки гонорари наших героїв невеликі, то кожний хоче витратити на таксі якомога менше грошей. Чіп може підсісти в таксі до Дейла і навпаки, якщо вони опинилися в одному місті. Оскільки у таксистів iLandii стала такса за кілометр, то витрати на шлях, який вони проїхали двоє, ділять на $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}$.

Приклади