Դուք հասել եք UJGOI-ի եզրափակիչ փուլ: մասնակիցներից (որոնք դասակարգված են 1, 2, \dots, n) յուրաքանչյուրին պետք է նշանակվի հասանելի դասարաններից մեկը: Չնայած որոշ մասնակիցներ արդեն նշանակվել են դասարան, դուք պետք է դասարաններ նշանակեք մնացած ուսանողների համար:
Այնուամենայնիվ, որպեսզի խուսափեք նման դասակարգված մասնակիցների խմբավորումից, ձեր վերջնական դասավորությունը a_1, a_2, \dots, a_n (որտեղ 1\le a_i\le k -րդ մասնակիցի դասարանը) պետք է բավարարի հետևյալ պայմանը: Յուրաքանչյուր շարունակական հատվածի (որտեղ 1 \le \ell < r \le n) համար, չպետք է լինի դասարան, որը հայտնվում է խիստ ավելի քան \frac{r-\ell+1}{2} անգամ — այսինքն, չպետք է լինի դասարան, որտեղ ուսանողների մեծամասնությունը դասավորված է:
Ձեր առաջադրանքը պարզել է դասավորություն, որը համապատասխանում է այս չափանիշներին:
Առաջին տողում կա մեկ ամբողջ թիվ (1\le n\le 2\cdot 10^5) — մասնակիցների թիվը:
Երկրորդ տողում կա մեկ ամբողջ թիվ (1\le k\le 10^6) — հասանելի դասարանների թիվը:
Երրորդ տողում կա ամբողջ թվեր a_1,~a_2,\dots,~a_n (0\le a_i\le k) — մասնակիցների դասավորությունը, որտեղ a_i=0 նշանակում է, որ նրա արժեքը դեռևս չի որոշվել:
Առաջին տողում, արտածեք "Այո" եթե կա դասավորություն, որը բավարարում է հայտարարությանը և "Ոչ" այլապես:
Եթե կա նման դասավորություն, ապա արտածեք փոփոխված a_1,\dots, a_n երկրորդ տողում:
Example 1
Example 2
Առաջին օրինակին, հնարավոր դասավորություններից մեկը a=[1, 2, \underline{4}, \underline{3}, 1] է: Օրինակ, եթե \ell=1 և r=3, ապա [a_1, a_2, a_3]=a[1..3]=[1,2,4] բավարարում է պայմանը, քանի որ յուրաքանչյուր տարր տեղի է ունենում միայն մեկ անգամ, մինչդեռ \frac{r-\ell+1}{2}=\frac{3-1+1}{2}=1.5 > 1: Դուք կարող եք ստուգել, որ պայմանը բավարարում է բոլոր 1\le \ell < r\le n համար:
Երկրորդ օրինակին, մենք կարող ենք ապացուցել, որ չկա դասավորություն, որը բավարարում է պայմանը: Օրինակ, եթե դասավորությունը a=[1, 2, \underline{3}, \underline{2}, 1] է, ապա a[2..4]=[2, 3, 2] չի բավարարում պայմանը: Երկու մասնակիցներ գտնվում են մեկ դասարանում, բայց \frac{r-\ell+1}{2}=1.5<2.
( միավոր): a_i \geq 1;
( միավոր): a_i = 0;
( միավոր): չկա i>1 այնպես, որ a_i = a_{i-1} = 0;
( միավոր): k > 5;
( միավոր): k \le 5;
( միավոր): առանց լրացուցիչ սահմանափակումների.