바이트자(Bajtocja)는 다시 한번 비토자(Bitocja)를 공격할 계획을 세우고 있습니다. 바이트그롬(Bajtogrom) 특수 부대에는 $n$명의 병사가 있으며, 오늘 아침 집합에서 일렬로 정렬했습니다. 강습 작전을 책임진 바이트자르(Bajtazar) 장군은 왼쪽부터 오른쪽으로 병사들의 위치에 1부터 $n$까지 번호를 매겼습니다.

각 병사는 강습을 수행할 준비가 되었거나, 법 개정에 따라 추가 훈련이 필요한 상태입니다. 바이트자르 장군은 강습 준비가 된 모든 병사가 대열에서 연속된 구간을 이루기를 원합니다. 더 형식적으로 말하면, $1 \le i < j < k \le n$인 세 위치에 대해 $i$번째와 $k$번째 병사는 준비되었지만 $j$번째 병사는 준비되지 않은 상황이 없기를 바랍니다.

이 조건이 기본적으로 충족되지 않을 수 있으므로, 바이트자르는 $m$개의 명령을 내릴 것입니다. $i$번째 명령에서 그는 위치 $a_i$와 $b_i$에 있는 병사들에게 서로 위치를 바꾸라고 지시합니다. 병사들은 $a_i$번째 병사가 강습 준비가 되었고 $b_i$번째 병사는 준비되지 않았을 때만 위치를 바꿉니다.

바이트자르는 이미 일련의 명령을 선택했으며 이를 실행하려고 합니다. 하지만 그는 현재 몇 명의 병사가 준비되었는지, 혹은 그들이 어느 위치에 있는지 알지 못합니다. 따라서 그는 $1$부터 $n$까지의 모든 정수 $k$에 대해 다음 문제를 해결하고자 합니다. 강습 준비가 된 병사가 정확히 $k$명인 모든 $\binom{n}{k}$가지 초기 구성에 대하여, 모든 명령을 수행한 후 바이트자르의 조건(강습 준비가 된 병사들이 대열에서 연속된 구간을 이룸)이 충족되는 구성은 몇 가지입니까? 그가 구하고자 하는 값을 계산해 주십시오!

참고: 포치츠키 알고리트미츠네(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

참고

예제 설명: 만약 처음에 단 한 명의 병사만 강습 준비가 되었다면, 그 병사는 확실히 (한 명으로 구성된) 연속된 구간을 이룰 것입니다. 반면, 두 명의 병사가 준비되어 최종적으로 서로 이웃하게 되는 상황은 존재하지 않습니다.

두 번째 병사를 제외한 모든 병사가 강습 준비가 된 상황을 고려해 봅시다. 첫 번째 명령은 병사들의 위치에 영향을 주지 않습니다. 두 번째 명령 후, 첫 번째 병사는 준비되었고 두 번째 병사는 준비되지 않았으므로 서로 위치를 바꿉니다. 세 번째 명령은 다시 아무런 효과가 없습니다. 이제 첫 번째 병사는 준비되지 않았고 네 번째 병사는 준비되었으므로, 마지막 명령에 의해 위치를 바꾸지 않습니다. 결과적으로 첫 번째 병사만 강습 준비가 되지 않은 상태가 됩니다. 이는 $k=3$일 때 바이트자르의 의도대로 끝나는 유일한 초기 구성입니다.

따라서 각 $k$에 대한 경우의 수는 수열 $[4, 0, 1, 1]$과 같습니다.