Aujourd'hui, participants du concours UJGOI se sont qualifiés pour la phase finale. Sakurako sait que chaque participant est soit heureux, soit malheureux à propos du concours. Elle a tâches, où la -ème tâche change l'humeur de tous les participants du \ell_i-ème au r_i-ème à l'opposé. Sakurako doit choisir un sous-ensemble de tâches de manière à ce que tous les participants soient heureux, mais cette tâche est trop difficile pour elle, alors elle demande votre aide.
La première ligne contient deux entiers et (1\le n,q\le 2\cdot 10^5) — le nombre de participants et de tâches.
La deuxième ligne contient entiers a_1, ~a_2, \dots, ~a_n (a_i=0 si le participant est heureux, a_i=1 sinon).
Chacune des lignes suivantes contient deux entiers \ell_i et r_i (1\le \ell_i\le r_i\le n).
S'il n'existe pas de tel sous-ensemble, imprimez "NO".
S'il existe un tel sous-ensemble, alors dans la première ligne, imprimez "YES". Dans la deuxième ligne, imprimez symboles "0" et "1". Le -ème symbole doit être "1" si vous souhaitez utiliser la -ème tâche, et "0" sinon. S'il y a plusieurs options — vous pouvez en imprimer n'importe laquelle.
Example 1
Example 2
Dans le premier exemple, la première tâche change l'humeur des deux premiers participants, voici comment le tableau va changer :
le premier participant changera d'humeur de à ;
le deuxième participant changera d'humeur de à ;
le troisième participant ne changera pas d'humeur;
le quatrième participant ne changera pas d'humeur.
Ainsi, le tableau résultant sera .
La deuxième tâche change l'humeur des deuxième et troisième participants, voici comment le tableau va changer :
le premier participant ne changera pas d'humeur.
le deuxième participant changera d'humeur de à ;
le troisième participant changera d'humeur de à ;
le quatrième participant ne changera pas d'humeur.
Ainsi, le tableau résultant sera .
( points): n\le 5;
( points): q \le 20;
( points): q \le 40;
( points): n \le 64;
( points): Tous les \ell_i sont différents;
( points): a_i = 1 pour tous les ;
( points): n,~q~\le~1000;
( points): sans contraintes supplémentaires.