Poçt islahatı
Flathlandiyada islahatlar dövrü davam edir. Yaxınlarda yol islahatı həyata keçirildi və indi ölkənin yolları ilə hər hansı bir şəhərdən digərinə yalnız bir yolla çatmaq mümkündür. Eyni zamanda, sehrbazların islahatı da baş tutdu və hər şəhərdə yalnız bir sehrbaz qaldı. İndi isə poçt sisteminin islahatı başladı.
Yeni yaranmış "Eks-Fedya" poçt agentliyi unikal bir xidmət təklif edir - kollektiv bağlama. Bu xidmət, adi bağlama qiymətinə, hər hansı bir yoldakı bütün şəhərlərin sakinlərinə bağlamalar göndərməyə imkan verir. Maraqlıdır ki, bu xidmətdən yalnız Flathlandiyanın sehrbazları istifadə etməyə başladılar və bir-birinə böyük miqdarda sehrli kaktuslar göndərməyə başladılar. Agentlik gözlənilməz bir problemlə üzləşdi: məlum olduğu kimi, bütün sehrbazlar qüllələrdə yaşayır və üstəlik, qüllələrində pilləkənlər tikmirlər, həm də zaman-zaman onların hündürlüyünü dəyişirlər. Buna görə də, hündürlüyü h olan qüllədə yaşayan sehrbaza bağlama çatdırmaq üçün agentliyin kuryerinin yanında ən azı h metr ip olmalıdır.
Sizə logistika şöbəsinə rəhbərlik etmək tapşırılıb - qüllələrin hündürlükləri və onların dəyişiklikləri haqqında mövcud məlumatlara əsasən, şəhərlər arasında i və j arasında bağlamalar çatdıran kuryerə verilməli olan minimum ip uzunluğunu müəyyən etməlisiniz.
Giriş verilənləri
Giriş faylının ilk sətiri Flathlandiyada şəhərlərin sayı olan n ədədini ehtiva edir (1 ≤ n ≤ 50000). İkinci sətirdə n müsbət ədəd var, bunlar şəhərlərdəki qüllələrin hündürlükləridir və 10^5-dən çox deyil. Növbəti n-1 sətirdə i-ci yolun təsviri olan iki ədəd u_i və v_i var, 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i. Növbəti sətirdə sorğuların sayı olan k ədəd var (1 ≤ k ≤ 100000). Növbəti k sətirdə sorğuların təsviri aşağıdakı formatda verilir:
Şəhər i-dən olan sehrbazın qülləsinin hündürlüyünün h olduğunu bildirməsi ! i h şəklindədir, 1 ≤ i ≤ n, 1 ≤ h ≤ 10^5.
Kuryerin i-dən j-yə qədər olan yolda bütün şəhərlərə bağlamalar çatdırmaq üçün ip verilməsi sorğusu ? i j şəklindədir, 1 ≤ i, j ≤ n.
Çıxış verilənləri
Bağlamaların çatdırılması sorğusu üçün hər biri üçün kuryerə verilməli olan minimum ip uzunluğunu çıxarın.