Bytecie (encore une fois) prévoit d'attaquer Bitocie. L'unité spéciale d'élite Bajtogrom compte $n$ soldats, qui se sont alignés en rang ce matin lors du rassemblement. Le général Bajtazar, responsable de l'opération de débarquement, a numéroté leurs positions de gauche à droite de $1$ à $n$.

Chaque soldat est soit prêt à effectuer le débarquement, soit a besoin d'une formation supplémentaire suite à une modification de la loi. Le général Bajtazar souhaiterait que tous les soldats prêts au débarquement forment un intervalle contigu du rang. Plus formellement, il souhaiterait qu'il n'existe aucun triplet de positions de soldats $1 \le i < j < k \le n$ tel que le $i$-ième et le $k$-ième soldat du rang soient prêts, mais pas le $j$-ième.

Comme cette condition peut ne pas être remplie par défaut, Bajtazar émettra $m$ ordres. Dans le $i$-ième ordre, il ordonnera aux soldats aux positions $a_i$ et $b_i$ de communiquer entre eux afin d'échanger leurs positions. Les soldats échangeront leurs positions si et seulement si le soldat à la position $a_i$ est prêt au débarquement et le soldat à la position $b_i$ ne l'est pas.

Bajtazar a déjà choisi une séquence d'ordres et a l'intention de les émettre. Cependant, il ne sait pas combien de soldats sont prêts au débarquement ni à quelles positions ils se trouvent. Pour chaque entier $k$ compris entre $1$ et $n$ inclus, il souhaiterait résoudre le problème suivant : considérons toutes les $\binom{n}{k}$ configurations initiales de soldats prêts et non préparés, dans lesquelles exactement $k$ soldats sont prêts au débarquement. Pour combien de ces configurations, après l'exécution de tous les ordres, la condition de Bajtazar sera-t-elle remplie (c'est-à-dire que les soldats prêts au débarquement formeront un intervalle contigu du rang) ? Aidez-le et calculez les valeurs qu'il recherche !

Remarque : Comme de nombreux programmeurs débutants participent aux Potyczki Algorytmiczne, nous avons décidé de ne pas vous tourmenter avec de grands nombres. Il suffit donc que pour chaque $k$, vous donniez le reste de la division du nombre de possibilités par le nombre premier $2$.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $m$ ($2 \le n \le 35$; $1 \le m \le 1\,000$), représentant respectivement le nombre de soldats dans le rang et le nombre d'ordres.

Les $m$ lignes suivantes contiennent les descriptions des ordres ; la $i$-ième de ces lignes contient deux entiers $a_i$ et $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), décrits dans l'énoncé du problème.

Sortie

La première et unique ligne de sortie doit contenir $n$ entiers séparés par des espaces ; le $k$-ième d'entre eux doit être égal au reste de la division par $2$ du nombre de configurations initiales de soldats, dans lesquelles exactement $k$ soldats sont prêts au débarquement et pour lesquelles, après l'exécution de tous les ordres, tous les soldats prêts forment un intervalle contigu du rang.

Exemples

Entrée 1

4 4
4 1
1 2
3 4
1 4

Sortie 1

0 0 1 1

Remarque

Si initialement un seul soldat est prêt au débarquement, il formera certainement un intervalle contigu (d'un seul élément). En revanche, il n'existe aucune situation où deux soldats sont prêts au débarquement et finissent par occuper des places adjacentes.

Considérons la situation où tous les soldats sauf le deuxième du rang sont prêts au débarquement. Le premier ordre n'affectera pas les positions des soldats. Après le deuxième ordre, comme le premier soldat du rang est prêt et le deuxième ne l'est pas, ils échangeront leurs places. Le troisième ordre n'aura à nouveau aucun effet. Comme maintenant le premier soldat du rang n'est pas prêt au débarquement et que le quatrième soldat du rang l'est, ils n'échangeront pas leurs places suite au dernier ordre. Finalement, seul le premier soldat du rang ne sera pas prêt au débarquement. C'est la seule configuration initiale pour $k = 3$ qui se termine selon les souhaits de Bajtazar.

Pour les $k$ suivants, les nombres de possibilités sont donc égaux à la séquence $[4, 0, 1, 1]$.