Today, participants of the UJGOI contest have qualified for the final stage. Sakurako knows that each participant is either happy or not about the contest. She has tasks, where the -th task changes the mood of all participants from the \ell_i-th to the r_i-th to the opposite. Sakurako needs to choose some subset of tasks in a way that all participants will be happy, but this task is too hard for her, so she asks for your help.
The first line contains two integers and (1\le n,q\le 2\cdot 10^5) — the number of participants and tasks.
The second line contains integers a_1, ~a_2, \dots, ~a_n (a_i=0 if the participant is happy, a_i=1 otherwise).
Each of the next lines contains two integers \ell_i and r_i (1\le \ell_i\le r_i\le n).
If there is no such subset, print "NO".
If there is such a subset, then in the first line, print "YES". In the second line, print symbols "0" and "1". The -th symbol should be "1" if you want to use the -th task, and "0" if not. If there are multiple options — you may print any of them.
Example 1
Example 2
In the first example, the first task changes the mood of the first two participants, so here is how the array will change:
the first participant will change mood from to ;
the second participant will change mood from to ;
the third participant will not change mood;
the fourth participant will not change mood.
So the resulting array will be .
The second task changes the mood of the second and third participants, so here is how the array will change:
the first participant will not change mood.
the second participant will change mood from to ;
the third participant will change mood from to ;
the fourth participant will not change mood.
So the resulting array will be .
( points): n\le 5;
( points): q \le 20;
( points): q \le 40;
( points): n \le 64;
( points): All \ell_i are different;
( points): a_i = 1 for all ;
( points): n,~q~\le~1000;
( points): without additional constraints.