Байтоция (в очередной раз) планирует нападение на Битоцию. В элитном спецподразделении «Байтогром» служат $n$ солдат, которые на утреннем построении выстроились в ряд. Генерал Байтазар, ответственный за проведение десанта, пронумеровал их позиции слева направо числами от 1 до $n$.

Каждый солдат либо готов к десанту, либо, в связи с поправками в законодательстве, нуждается в дополнительной подготовке. Генерал Байтазар хочет, чтобы все солдаты, готовые к десанту, занимали связный отрезок ряда. Формально, он хочет, чтобы не существовало такой тройки позиций $1 \le i < j < k \le n$, что $i$-й и $k$-й солдаты в ряду готовы к десанту, а $j$-й — нет.

Поскольку это условие может не выполняться изначально, Байтазар отдаст $m$ приказов. В $i$-м из них он прикажет солдатам на позициях $a_i$ и $b_i$ обменяться местами. Солдаты поменяются местами тогда и только тогда, когда солдат на позиции $a_i$ готов к десанту, а солдат на позиции $b_i$ — нет.

Байтазар уже выбрал последовательность приказов и собирается их отдать. Однако он не знает, сколько солдат готовы к десанту и на каких позициях они находятся. Поэтому для каждого целого числа $k$ от 1 до $n$ включительно он хочет решить следующую задачу: рассмотрим все $\binom{n}{k}$ начальных конфигураций готовых и не готовых к десанту солдат, в которых к десанту готовы ровно $k$ солдат. Для скольких из этих конфигураций после выполнения всех приказов условие Байтазара будет выполнено (то есть солдаты, готовые к десанту, будут составлять связный отрезок ряда)? Помогите ему и вычислите искомые значения!

Примечание: Поскольку в «Potyczki Algorytmiczne» участвует много начинающих программистов, мы решили не утомлять вас большими числами. Достаточно того, что для каждого $k$ вы укажете остаток от деления количества возможностей на простое число 2.

Входные данные

В первой строке входных данных находятся два целых числа $n$ и $m$ ($2 \le n \le 35$; $1 \le m \le 1000$), обозначающие количество солдат в ряду и количество приказов соответственно.

В следующих $m$ строках содержатся описания приказов; $i$-я из этих строк содержит два целых числа $a_i$ и $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), описанные в условии задачи.

Выходные данные

В единственной строке вывода должны находиться $n$ целых чисел, разделенных одиночными пробелами; $k$-е из них должно быть равно остатку от деления на 2 количества начальных конфигураций солдат, в которых ровно $k$ солдат готовы к десанту и для которых после выполнения всех приказов все готовые солдаты образуют связный отрезок ряда.

Примеры

Пример 1

4 4
4 1
1 2
3 4
1 4

Выходные данные 1

0 0 1 1

Примечание

Если изначально к десанту готов только один солдат, то он, безусловно, будет составлять (одноэлементный) связный отрезок ряда. Однако не существует ситуации, в которой к десанту готовы двое солдат и в итоге они окажутся рядом.

Рассмотрим ситуацию, в которой все солдаты, кроме второго, готовы к десанту. Первый приказ не повлияет на позиции солдат. После второго приказа, поскольку первый солдат в ряду готов, а второй — нет, они поменяются местами. Третий приказ снова не даст эффекта. Поскольку теперь первый солдат в ряду не готов к десанту, а четвертый готов, они не поменяются местами в результате последнего приказа. В итоге только первый солдат в ряду не будет готов к десанту. Это единственная начальная конфигурация для $k = 3$, заканчивающаяся согласно замыслу Байтазара.

Для остальных $k$ количества возможностей равны последовательности $[4, 0, 1, 1]$.