Alp vadisi

Alp dağlarının vadisində n kənd (nömrələnmiş 1 ... n) var və bu kəndlər yalnız n - 1 yol ilə birləşdirilib. Hər kənddən digərinə çatmaq mümkündür, lakin bu, çox vaxt ala bilər. Bu, xüsusilə zəruri əşyaları almaq lazım olduqda narahatlıq yaradır, çünki mağazalar yalnız s kənddə yerləşir.

Bu qış vəziyyət güclü qar yağışı səbəbindən daha da pisləşib. Buna görə də vadini tərk etmək, yəni vadini xarici dünya ilə birləşdirən dağ keçidindəki yeganə e kəndinə çatmaq və ya ən azı növbəti aylar üçün kifayət qədər ehtiyat almaq məqsədəuyğun olardı. Bu səhər radiodan eşitdiniz ki, qar səbəbindən n - 1 yoldan biri istifadəyə yararsız hala gəlib - lakin hansı yol olduğunu dəqiq başa düşə bilmədiniz.

İndi siz və dostlarınız vadini tərk edə biləcəyinizi bilmək istəyirsiniz, əgər yoxsa, hər birinizin mağazası olan kəndə çatmaq üçün nə qədər yol getməli olduğunuzu bilmək istəyirsiniz. Hansı yolun bloklandığını bilmirsiniz və dostlarınız vadinin müxtəlif kəndlərində yaşayır. q kənd və bloklanmış yol kombinasiyaları üçün bu suala cavab verən proqram yazın.

Giriş məlumatları

Birinci sətir tam ədədləri n (1 ≤ n ≤ 10^5), s, q (1 ≤ q ≤ 10^5) və e ehtiva edir, burada n - kəndlərin sayı, s (1 ≤ s ≤ n) - mağazaların sayı, q - proqramınıza sorğuların sayı və e (1 ≤ e ≤ n) - vadini tərk etmək üçün çatmalı olduğunuz kənddir.

Növbəti n - 1 sətir hər biri üç tam ədəd a, b və w ehtiva edir. Onlar a və b kəndlərini birləşdirən yolun uzunluğunun w olduğunu göstərir (1 ≤ w ≤ 10^9).

Daha sonra s sətir gəlir: hər biri bir tam ədəd c ehtiva edir ki, bu da c kəndində (1 ≤ c ≤ n) mağaza olduğunu göstərir. Bütün bu sətirlər fərqlidir, yəni heç bir kənddə birdən çox mağaza yoxdur.

Nəhayət, q növbəti sətirin hər biri iki tam ədəd i və r ehtiva edir, bu da i-ci yolun (1 ≤ i < n, sadalanma sırasına görə nömrələnmiş) artıq aktiv olmadığını və dostlarınızın r kəndində (1 ≤ r ≤ n) yaşadığını, vadini tərk edə biləcəyinizi və əgər cavab mənfi olarsa, mağazası olan kəndin nə qədər uzaqda olduğunu bilmək istəyirsiniz.

Çıxış məlumatları

q sətir çıxarın. i - ci sətir i - ci sorğuya cavab verməlidir. Müvafiq sətir "escape" (tırnaq işarələri olmadan) sözünü ehtiva etməlidir, əgər vadini tərk etmək imkanı varsa; əgər yoxsa, ən yaxın mağazası olan kəndə olan məsafəni və ya mağazaya çatmaq mümkün deyilsə "oo" sözünü ehtiva etməlidir.

İzah

Şəkildə yol istifadəyə yararsız hala gəlməzdən əvvəlki vəziyyət göstərilib. Mağazası olan kəndlər boz rəngdə göstərilib. Yollar "indeks / uzunluq" kimi işarələnib. Vadidən çıxış 1 kəndindədir.