UJGOI Müsabiqəsi#408

UJGOI Müsabiqəsi

1 saniyə
256 meqabayt
Very hard

Bu gün, UJGOI müsabiqəsinin iştirakçısı final mərhələsinə keçib. Sakurako bilir ki, hər bir iştirakçı müsabiqədən ya məmnundur, ya da deyil. Onun tapşırığı var, burada -ci tapşırıq \ell_i-ci iştirakçıdan r_i-ci iştirakçıya qədər olan bütün iştirakçıların ruh halını əksinə çevirir. Sakurako tapşırıqların, bütün iştirakçıların məmnun olacağı, müəyyən alt çoxluğunu seçməlidir, amma bu tapşırıq onun üçün çox çətindir, ona görə də sizdən kömək istəyir.

Input

Birinci sətirdə iki tam ədəd və (1\le n,q\le 2\cdot 10^5) — iştirakçıların və tapşırıqların sayı verilir.

İkinci sətirdə tam ədəd a_1, ~a_2, \dots, ~a_n (əgər iştirakçı məmnundursa a_i=0, əks halda a_i=1) verilir.

Sonrakı sətrin hər biri iki tam ədəd \ell_i və r_i (1\le \ell_i\le r_i\le n) ehtiva edir.

Output

Əgər belə bir alt çoxluq yoxdursa, "NO" çap edin.

Əgər belə bir alt çoxluq varsa, birinci sətirdə "YES" çap edin. İkinci sətirdə simvol "0" və "1" çap edin. Əgər -ci tapşırığı istifadə etmək istəyirsinizsə -ci simvol "1", əks halda "0" olmalıdır. Əgər bir neçə seçim varsa — istənilən birini çap edə bilərsiniz.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Birinci nümunədə, birinci tapşırıq ilk iki iştirakçının ruh halını dəyişir, beləliklə, massiv aşağıdakı kimi dəyişəcək:

  • birinci iştirakçı ruh halını -dən -a dəyişəcək;

  • ikinci iştirakçı ruh halını -dan -ə dəyişəcək;

  • üçüncü iştirakçı ruh halını dəyişməyəcək;

  • dördüncü iştirakçı ruh halını dəyişməyəcək.

Nəticədə massiv olacaq.

İkinci tapşırıq ikinci və üçüncü iştirakçıların ruh halını dəyişir, beləliklə, massiv aşağıdakı kimi dəyişəcək:

  • birinci iştirakçı ruh halını dəyişməyəcək.

  • ikinci iştirakçı ruh halını -dən -a dəyişəcək;

  • üçüncü iştirakçı ruh halını -dən -a dəyişəcək;

  • dördüncü iştirakçı ruh halını dəyişməyəcək.

Nəticədə massiv olacaq.

Scoring

  1. ( bal): n\le 5;

  2. ( bal): q \le 20;

  3. ( bal): q \le 40;

  4. ( bal): n \le 64;

  5. ( bal): bütün \ell_i-lər fərqlidir;

  6. ( bal): a_i = 1 bütün -lər üçün;

  7. ( bal): n,~q~\le~1000;

  8. ( bal): əlavə məhdudiyyətlər olmadan.