UJGOI Կրակովում#406

UJGOI Կրակովում

1 վայրկյան
256 մեգաբայթ
Very hard

Դուք հասել եք 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} անգամ — այսինքն, չպետք է լինի դասարան, որտեղ ուսանողների մեծամասնությունը դասավորված է:

Ձեր առաջադրանքը պարզել է դասավորություն, որը համապատասխանում է այս չափանիշներին:

Input

Առաջին տողում կա մեկ ամբողջ թիվ (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 նշանակում է, որ նրա արժեքը դեռևս չի որոշվել:

Output

Առաջին տողում, արտածեք "Այո" եթե կա դասավորություն, որը բավարարում է հայտարարությանը և "Ոչ" այլապես:

Եթե կա նման դասավորություն, ապա արտածեք փոփոխված a_1,\dots, a_n երկրորդ տողում:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Առաջին օրինակին, հնարավոր դասավորություններից մեկը 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.

Scoring

  1. ( միավոր): a_i \geq 1;

  2. ( միավոր): a_i = 0;

  3. ( միավոր): չկա i>1 այնպես, որ a_i = a_{i-1} = 0;

  4. ( միավոր): k > 5;

  5. ( միավոր): k \le 5;

  6. ( միավոր): առանց լրացուցիչ սահմանափակումների.