UJGOI մրցույթ#408

UJGOI մրցույթ

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

Այսօր UJGOI մրցույթի մասնակիցներ որակավորվել են եզրափակիչ փուլ: Սակուրակոն գիտի, որ յուրաքանչյուր մասնակից կամ ուրախ է, կամ ոչ: Նա ունի առաջադրանք, որտեղ -րդ առաջադրանքը փոխում է բոլոր մասնակիցների տրամադրությունը \ell_i-րդից մինչև r_i-րդ հակառակին: Սակուրակոն պետք է ընտրի որոշակի առաջադրանքների ենթախումբ այնպես, որ բոլոր մասնակիցները ուրախ լինեն, բայց այս առաջադրանքը շատ դժվար է նրա համար, ուստի նա խնդրում է ձեր օգնությունը:

Input

Առաջին տողը պարունակում է երկու ամբողջ թիվ և (1\le n,q\le 2\cdot 10^5) — մասնակիցների և առաջադրանքների թիվը:

Երկրորդ տողը պարունակում է ամբողջ թիվ a_1, ~a_2, \dots, ~a_n (a_i=0, եթե մասնակիցը ուրախ է, a_i=1 հակառակ դեպքում):

Հաջորդ տողերը պարունակում են երկու ամբողջ թիվ \ell_i և r_i (1\le \ell_i\le r_i\le n):

Output

Եթե նման ենթախումբ չկա, տպեք "ՈՉ":

Եթե նման ենթախումբ կա, ապա առաջին տողում տպեք "Այո". Երկրորդ տողում տպեք խորհրդանիշ "0" և "1". -րդ խորհրդանիշը պետք է լինի "1", եթե ցանկանում եք օգտագործել -րդ առաջադրանքը, և "0", եթե ոչ: Եթե կան մի քանի տարբերակներ — կարող եք տպել դրանցից որևէ մեկը:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Առաջին օրինակին, առաջին առաջադրանքը փոխում է առաջին երկու մասնակիցների տրամադրությունը, այնպես որ ահա թե ինչպես է զանգվածը փոխվելու.

  • առաջին մասնակիցը փոխում է տրամադրությունը -ից ;

  • երկրորդ մասնակիցը փոխում է տրամադրությունը -ից ;

  • երրորդ մասնակիցը չի փոխում տրամադրությունը;

  • չորրորդ մասնակիցը չի փոխում տրամադրությունը.

Այսպիսով, արդյունք հանդիսացող զանգվածը կլինի :

Երկրորդ առաջադրանքը փոխում է երկրորդ և երրորդ մասնակիցների տրամադրությունը, այնպես որ ահա թե ինչպես է զանգվածը փոխվելու:

  • առաջին մասնակիցը չի փոխում տրամադրությունը.

  • երկրորդ մասնակիցը փոխում է տրամադրությունը -ից ;

  • երրորդ մասնակիցը փոխում է տրամադրությունը -ից ;

  • չորրորդ մասնակիցը չի փոխում տրամադրությունը.

Այսպիսով, արդյունք հանդիսացող զանգվածը կլինի .

Scoring

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

  2. ( միավոր): q \le 20;

  3. ( միավոր): q \le 40;

  4. ( միավոր): n \le 64;

  5. ( միավոր): Բոլոր \ell_i-ները տարբեր են;

  6. ( միավոր): a_i = 1 բոլոր -ների համար;

  7. ( միավոր): n,~q~\le~1000;

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