Bajtocja (una vez más) planea atacar Bitocja. La unidad de élite Bajtogrom cuenta con $n$ soldados, quienes se han formado en una fila durante la reunión de esta mañana. El General Bajtazar, responsable de llevar a cabo el desembarco, ha numerado sus posiciones de izquierda a derecha con números del 1 al $n$.

Cada soldado está listo para realizar el desembarco o, debido a una enmienda en la ley, necesita entrenamiento adicional. El General Bajtazar desea que todos los soldados listos para el desembarco formen un intervalo contiguo en la fila. Formalmente, desea que no exista un trío de posiciones de soldados $1 \le i < j < k \le n$ tal que el soldado en la posición $i$ y el soldado en la posición $k$ estén listos, mientras que el soldado en la posición $j$ no lo esté.

Dado que esta condición puede no cumplirse inicialmente, Bajtazar emitirá $m$ órdenes. En la $i$-ésima orden, ordenará a los soldados en las posiciones $a_i$ y $b_i$ comunicarse entre sí para intercambiar sus posiciones. Los soldados intercambiarán sus posiciones si y solo si el soldado en la posición $a_i$ está listo para el desembarco y el soldado en la posición $b_i$ no lo está.

Bajtazar ya ha elegido una secuencia de órdenes y tiene la intención de emitirlas. Sin embargo, no sabe cuántos soldados están listos para el desembarco ni en qué posiciones se encuentran. Por lo tanto, para cada número entero $k$ entre 1 y $n$ inclusive, le gustaría resolver el siguiente problema: consideremos todas las $\binom{n}{k}$ configuraciones iniciales de soldados listos y no preparados, en las cuales hay exactamente $k$ soldados listos para el desembarco. ¿Para cuántas de estas configuraciones, después de ejecutar todas las órdenes, se cumplirá la condición de Bajtazar (es decir, los soldados listos para el desembarco formarán un intervalo contiguo en la fila)? ¡Ayúdale y calcula los valores que busca!

Nota: Dado que muchos programadores principiantes participan en las Potyczki Algorytmiczne, hemos decidido no abrumarlos con números grandes. Por lo tanto, basta con que para cada $k$ proporciones el resto de la división del número de posibilidades entre el número primo 2.

Entrada

La primera línea de la entrada contiene dos números enteros $n$ y $m$ ($2 \le n \le 35$; $1 \le m \le 1\,000$), que representan el número de soldados en la fila y el número de órdenes, respectivamente.

En las siguientes $m$ líneas se encuentran las descripciones de las órdenes; la $i$-ésima de estas líneas contiene dos números enteros $a_i$ y $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), descritos en el enunciado del problema.

Salida

En la primera y única línea de salida debe haber $n$ números enteros separados por espacios individuales; el $k$-ésimo de ellos debe ser igual al resto de la división entre 2 del número de configuraciones iniciales de soldados en las que exactamente $k$ soldados están listos para el desembarco y para las cuales, después de ejecutar todas las órdenes, todos los soldados listos forman un intervalo contiguo en la fila.

Ejemplos

Entrada 1

4 4
4 1
1 2
3 4
1 4

Salida 1

0 0 1 1

Nota

Si inicialmente solo un soldado está listo para el desembarco, ciertamente formará un intervalo contiguo (de un solo elemento) en la fila. Por otro lado, no existe una situación en la que dos soldados estén listos para el desembarco y finalmente terminen ocupando lugares adyacentes.

Consideremos la situación en la que todos los soldados, excepto el segundo en la fila, están listos para el desembarco. La primera orden no afectará las posiciones de los soldados. Después de la segunda orden, dado que el primer soldado en la fila está listo y el segundo no, intercambiarán sus lugares. La tercera orden nuevamente no tendrá efecto. Dado que ahora el primer soldado en la fila no está listo para el desembarco y el cuarto soldado en la fila sí lo está, no intercambiarán sus lugares como resultado de la última orden. Finalmente, solo el primer soldado en la fila no estará listo para el desembarco. Esta es la única configuración inicial para $k = 3$ que termina cumpliendo el plan de Bajtazar.

Para los siguientes $k$, los números de posibilidades son, por lo tanto, iguales a la secuencia $[4, 0, 1, 1]$.