Concours UJGOI#408

Concours UJGOI

1 seconde
256 mégaoctets
Very hard

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.

Input

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).

Output

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.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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 .

Scoring

  1. ( points): n\le 5;

  2. ( points): q \le 20;

  3. ( points): q \le 40;

  4. ( points): n \le 64;

  5. ( points): Tous les \ell_i sont différents;

  6. ( points): a_i = 1 pour tous les ;

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

  8. ( points): sans contraintes supplémentaires.