Այսօր UJGOI մրցույթի մասնակիցներ որակավորվել են եզրափակիչ փուլ: Սակուրակոն գիտի, որ յուրաքանչյուր մասնակից կամ ուրախ է, կամ ոչ: Նա ունի առաջադրանք, որտեղ -րդ առաջադրանքը փոխում է բոլոր մասնակիցների տրամադրությունը \ell_i-րդից մինչև r_i-րդ հակառակին: Սակուրակոն պետք է ընտրի որոշակի առաջադրանքների ենթախումբ այնպես, որ բոլոր մասնակիցները ուրախ լինեն, բայց այս առաջադրանքը շատ դժվար է նրա համար, ուստի նա խնդրում է ձեր օգնությունը:
Առաջին տողը պարունակում է երկու ամբողջ թիվ և (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):
Եթե նման ենթախումբ չկա, տպեք "ՈՉ":
Եթե նման ենթախումբ կա, ապա առաջին տողում տպեք "Այո". Երկրորդ տողում տպեք խորհրդանիշ "0" և "1". -րդ խորհրդանիշը պետք է լինի "1", եթե ցանկանում եք օգտագործել -րդ առաջադրանքը, և "0", եթե ոչ: Եթե կան մի քանի տարբերակներ — կարող եք տպել դրանցից որևէ մեկը:
Example 1
Example 2
Առաջին օրինակին, առաջին առաջադրանքը փոխում է առաջին երկու մասնակիցների տրամադրությունը, այնպես որ ահա թե ինչպես է զանգվածը փոխվելու.
առաջին մասնակիցը փոխում է տրամադրությունը -ից ;
երկրորդ մասնակիցը փոխում է տրամադրությունը -ից ;
երրորդ մասնակիցը չի փոխում տրամադրությունը;
չորրորդ մասնակիցը չի փոխում տրամադրությունը.
Այսպիսով, արդյունք հանդիսացող զանգվածը կլինի :
Երկրորդ առաջադրանքը փոխում է երկրորդ և երրորդ մասնակիցների տրամադրությունը, այնպես որ ահա թե ինչպես է զանգվածը փոխվելու:
առաջին մասնակիցը չի փոխում տրամադրությունը.
երկրորդ մասնակիցը փոխում է տրամադրությունը -ից ;
երրորդ մասնակիցը փոխում է տրամադրությունը -ից ;
չորրորդ մասնակիցը չի փոխում տրամադրությունը.
Այսպիսով, արդյունք հանդիսացող զանգվածը կլինի .
( միավոր): n\le 5;
( միավոր): q \le 20;
( միավոր): q \le 40;
( միավոր): n \le 64;
( միավոր): Բոլոր \ell_i-ները տարբեր են;
( միավոր): a_i = 1 բոլոր -ների համար;
( միավոր): n,~q~\le~1000;
( միավոր): առանց լրացուցիչ սահմանափակումների.