Լևոնը և օղաբլիթները

Լևոնը շատ է սիրում օղաբլիթներ և գնացել է խանութ դրանց ետևից։ Օղաբլիթներ վաճառողը՝ պարոն Օղակը, խաղամոլ է, և Լևոնին առաջարկում է խաղ, որում հաղթելու դեպքում նա կվաստակի իր օղաբլիթը։ Խաղը հետևյալն է՝ տրված է ծառ , որի աﬔն կողի վրա գրված է ﬔկ թիվ, որը ցույց է տալիս, թե քանի խնձոր կա այդ կողի վրա։ Ծառի վրա կա մարդուկ, ով սկզբում գտնվում է 1 համարով գագաթի վրա։ Խաղի ընթացքում Լևոնը և պարոն Օղակը մարդուկին տեղափոխում են մարդուկի ընթացիկ գագաթին հարևան գագաթ, որտեղ մարդուկը դեռ չի եղել։ Կողով անցնելիս մարդուկը ուտում է այդ կողի վրա գտնվող բոլոր խնձորները։ Խաղը սկսում է պարոն Օղակը։ Լևոնը և պարոն Օղակը կատարում են իրենց քայլերը ﬕմյանց հաջորդելով։ Խաղն ավարտվում է, երբ խաղացողը այլևս չի կարող քայլ կատարել։ Ամբողջ ընթացքում մարդուկի կերած խնձորների քանակը նշանակենք x-ով։ Լևոնը հաղթում է, եթե x-ի ﬓացորդը k-ի վրա փոքր է a-ից։ Հակառակ դեպքում հաղթում է պարոն Օղակը։ Բայց քանի որ պարոն Օղակը գիտի, որ Լևոնը շատ խելացի է, նա դժվարացրել է խնդրի պայմանները։ Նա որոշել է, որ նրանք պետք է ﬕանգաﬕց անեն q-ական քայլ (հնարավոր է, որ վերջին խաղացողը կատարի q-ից քիչ քայլ)։ Ձեր խնդիրն է տրված ծառի, k-ի, a-ի և q-ի համար պարզել, թե ով կհաղթի, եթե երկուսն էլ օպտիմալ խաղան։

Մուտքային տվյալներ

Մուտքի առաջին տողում տրված են n , k , a և q թվերը (1 ≤ a < k, 1 ≤ q < n) ։ Հաջորդող n-1 տողերում տրված է գրաֆի նկարագրությունը։ Աﬔն տողում տրված են v1 , v2 և c թվերը, ինչը նշանակում է, որ կա կող v1 և v2 գագաթների ﬕջև, որի վրա կա c հատ խնձոր (1 ≤ v1, v2 ≤ n, v1 ≠ v2, 0 ≤ c ≤ $10^9$ ) ։

Ելքային տվյալներ

Ելքի ﬕակ տողում պետք է տպել 1 բառ՝ Levon, եթե կհաղթի Լևոնը և MrCircle, եթե կհաղթի Պարոն Օղակը։

Սահմանափակումներ

• Թեստերի առաջին խմբի համար $2 ≤ n ≤ 10 , k = 2 , q = 1$։

• Թեստերի երկրորդ խմբի համար $2 ≤ n ≤ 10^9, 2 ≤ k ≤ 10^9$, ծառը շղթա է։

• Թեստերի երրորդ խմբի համար $2 ≤ n ≤ 10^4, 2 ≤ k ≤ 100$։

• Թեստերի չորորդ խմբի համար $2 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^9, q = 1$։

• Թեստերի հիգերորդ խմբի համար $2 ≤ n ≤ 10^5 , 2 ≤ k ≤ 10^9$։

Օրինակ

Աղբյուրը. հանրապետական 2018 եզրափակիչ փուլ