Kinoya yürüş

Çip və Deyl iLandia ölkəsində hamıya kömək edirlər. Növbəti dəfə öz işlərini uğurlu başa çatdirdiqdan sonra kinoya getməyi qərara aldılar. Amma onlar gözlənilməz hal ilə rastlaşdılar! Ölkədə yalnız bir kinoteatr var ki, o da paytaxtda yerləşir. Çip $x$ şəhərində, Deyl isə $y$ şəhərində öz macəralarını başa vurdular və kinoya vaxtında çatmaq üçün hər biri taksi sifariş etməyi qərara aldılar. Qəhramanlarımızın pulu az olduğundan, hər biri taksiyə bacardıgı qədər az pul xərcləmək istəyirdi. Əgər onlar eyni bir şəhərdə görüşə bilsələr, Çip Deylin olduğu taksiyə otura bilər və ya əksinə... iLandia ölkəsində bütün şəhərlərdə bir kilometr üçün ödəniş haqqı eyni olduğundan, Çip və Deyl birgə getdiyi yolun pulunu $2$-yə bölə bilərlər. Sizə Çip və Deylin müxtəlif şəhərlərdə macəralarının bir neçə ssenarisi verilir. Hər bir ssenari üçün qəhramanların minimal qonorarını hesablamaq lazımdır ki, onlar kinoya gedə bilsinlər.

İxtiyari iki şəhər arasında yalnız bir yol var. İki qonşu şəhər arasındakı məsafə $1$ kilometrdir. Paytaxtin nömrəsi $1$-dir.

Giriş verilənləri

Birinci sətirdə iki natural ədəd verilir: şəhərlərin sayı $n(1\le n\le 10^5)$ və $1$ kilometrin qiyməti $Price(1\le Price\le 10^4)$. Hər bir növbəti $n-1$ sətir isə $2$ natural ədəddən ibarətdir: $x$ və $y(1\le x,y\le n)$, $x$ şəhərindən $y$ şəhərinə gedən yolu göstərir. Bütun yollar ikitərəflidir. Növbəti sətirdə ssenarilərin sayı $q(1\le q\le 10^5)$ verilir. Hər bir ssenari yeni sətirdən başlayır və Çip və Deylin öz macəralaralarını bitirdiyi şəhərlərin $c$ və $d(1\le c,d\le n)$ nömrələri ilə verilir.

Çıxış verilənləri

İki ədəd ekrana verilməlidir: Çip və Deylin $10^{-5}$ dəqiqliyi ilə yola sərf etdikləri xərclər.

Nümunələr