Լևոնը և օղաբլիթները
Լևոնը շատ է սիրում օղաբլիթներ և գնացել է խանութ դրանց ետևից։ Օղաբլիթներ վաճառողը՝ պարոն Օղակը, խաղամոլ է, և Լևոնին առաջարկում է խաղ, որում հաղթելու դեպքում նա կվաստակի իր օղաբլիթը։ Խաղը հետևյալն է՝ տրված է ծառ , որի աﬔն կողի վրա գրված է ﬔկ թիվ, որը ցույց է տալիս, թե քանի խնձոր կա այդ կողի վրա։ Ծառի վրա կա մարդուկ, ով սկզբում գտնվում է 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 ≤ ) ։Ելքային տվյալներ
Ելքի ﬕակ տողում պետք է տպել 1 բառ՝
Levon, եթե կհաղթի Լևոնը և MrCircle, եթե կհաղթի Պարոն Օղակը։Սահմանափակումներ
- Թեստերի առաջին խմբի համար
։
- Թեստերի երկրորդ խմբի համար
, ծառը շղթա է։
- Թեստերի երրորդ խմբի համար
։
- Թեստերի չորորդ խմբի համար
։
- Թեստերի հիգերորդ խմբի համար
։
Օրինակ
Մուտք | Ելք |
7 2 1 2
1 2 3
2 3 2
1 4 1
4 5 0
4 6 7
6 7 2 | MrCircle |
Աղբյուրը. հանրապետական 2018 եզրափակիչ փուլ
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB