Süd Ziyarətləri (Gümüş)
Fermer Con, n təsərrüfat qurmağı planlaşdırır və bu təsərrüfatlar n - 1 yol ilə bir-birinə bağlanacaq, ağac şəklində (yəni, bütün təsərrüfatlar bir-birinə çatır, dövr yoxdur). Hər təsərrüfatda Guernsey və ya Holstein cinsindən olan inək var.
Fermer Conun m dostu onu tez-tez ziyarət edir. Dostu i ziyarət edərkən, fermer Con onunla təsərrüfat A[i]-dən təsərrüfat B[i]-ə qədər unikal yol dəsti ilə gedəcək (mümkün ki, A[i] = B[i]). Bundan əlavə, onlar yol boyunca istənilən inəyin südünü dadmaq imkanı əldə edəcəklər. Fermer Conun dostlarının əksəriyyəti də fermer olduğundan, süd seçimlərində çox güclü üstünlükləri var. Onun bəzi dostları yalnız Guernsey südü içəcək, digərləri isə yalnız Holstein südü içəcək. Fermer Conun hər hansı bir dostu yalnız ziyarət zamanı üstünlük verdiyi süd növünü içə bilsə xoşbəxt olacaq.
Hər bir dostun ziyarət nəticəsində xoşbəxt olub-olmayacağını müəyyən edin.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) və m (1 ≤ m ≤ 10^5) tam ədədlərini ehtiva edir. İkinci sətir uzunluğu n olan bir sətirdir. i - ci sətirin simvolu 'G'-dir, əgər i - ci təsərrüfatda Guernsey inəyi varsa, və 'H'-dir, əgər Holstein inəyi varsa.
Növbəti n - 1 sətir iki fərqli tam ədəd x və y (1 ≤ x, y ≤ n) ehtiva edir, bu da təsərrüfatlar x və y arasında yol olduğunu göstərir.
Növbəti m sətir tam ədədlər A[i], B[i] və simvol C[i] ehtiva edir. A[i] və B[i] dost i ziyarəti zamanı keçilən yolun son nöqtələrini təmsil edir, C[i] isə G və ya H-dir, əgər i - ci dost Guernsey südünü və ya Holstein südünü üstün tutursa.
Çıxış Məlumatları
Uzunluğu m olan ikili bir sətir çıxarın. i - ci sətirin simvolu '1' olmalıdır, əgər i - ci dost xoşbəxt olacaqsa, və '0' əks halda.
Nümunə
Təsərrüfat 1-dən təsərrüfat 4-ə yol təsərrüfatlar 1, 2 və 4-ü əhatə edir. Onların hamısı Holstein inəklərini ehtiva edir, buna görə birinci dost məmnun olacaq, amma ikinci dost olmayacaq.