Bajtocja 再次计划进攻 Bitocja。精锐特种部队 Bajtogrom 拥有 $n$ 名士兵，他们在今天的晨会上排成了一列。负责执行登陆任务的 Bajtazar 将军从左到右将他们的位置编号为 $1$ 到 $n$。

每名士兵要么已准备好执行登陆任务，要么因法律修订需要额外训练。Bajtazar 将军希望所有准备好登陆的士兵在队列中占据一个连续的区间。更正式地说，他希望不存在这样的三个士兵位置 $1 \le i < j < k \le n$，使得第 $i$ 位和第 $k$ 位士兵已准备好，而第 $j$ 位士兵未准备好。

由于该条件可能默认不满足，Bajtazar 将下达 $m$ 条指令。在第 $i$ 条指令中，他命令位于位置 $a_i$ 和 $b_i$ 的士兵进行交流以交换位置。仅当第 $a_i$ 位的士兵已准备好而第 $b_i$ 位的士兵未准备好时，他们才会交换位置。

Bajtazar 已经选定了一系列指令并打算下达。然而，他不知道有多少士兵准备好了登陆，也不知道他们分别在哪些位置。因此，对于 $1$ 到 $n$ 之间的每个整数 $k$，他想解决以下问题：考虑所有 $\binom{n}{k}$ 种初始配置（其中恰好有 $k$ 名士兵准备好登陆），在执行完所有指令后，有多少种配置满足 Bajtazar 的条件（即准备好登陆的士兵形成一个连续的区间）？请帮助他计算这些值！

注意：由于许多初学者程序员参加了 Potyczki Algorytmiczne，我们决定不让大数困扰你们。因此，对于每个 $k$，你只需输出满足条件的配置数量除以 $2$ 的余数。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 35; 1 \le m \le 1\,000$)，分别表示队列中的士兵人数和指令数。

接下来的 $m$ 行描述了指令；第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$)，含义如题所述。

输出格式

输出一行，包含 $n$ 个整数，用空格隔开；第 $k$ 个数应等于初始配置中恰好有 $k$ 名士兵准备好登陆，且在执行完所有指令后，所有准备好的士兵形成一个连续区间的配置数量除以 $2$ 的余数。

样例

输入 1

4 4
4 1
1 2
3 4
1 4

输出 1

0 0 1 1

说明 1

如果最初只有一名士兵准备好登陆，那么他肯定会构成一个（单元素的）连续区间。不存在两名士兵准备好登陆且最终相邻的情况。

考虑除队列中第二名士兵外，其余所有士兵都准备好登陆的情况。第一条指令不会影响士兵的位置。执行第二条指令后，由于队列中第一名士兵已准备好而第二名士兵未准备好，他们会交换位置。第三条指令同样不会产生效果。由于此时队列中第一名士兵未准备好而第四名士兵已准备好，他们不会在最后一条指令中交换位置。最终，只有队列中第一名士兵未准备好。这是 $k=3$ 时唯一符合 Bajtazar 预期的初始配置。

因此，对于后续的 $k$，可能性的数量分别为 $[4, 0, 1, 1]$。