Bajtocja (một lần nữa) đang lên kế hoạch tấn công Bitocja. Đơn vị đặc nhiệm tinh nhuệ Bajtogrom bao gồm $n$ người lính, những người đã xếp hàng trong buổi tập trung sáng nay. Tướng Bajtazar, người chịu trách nhiệm thực hiện cuộc đổ bộ, đã đánh số các vị trí của họ từ trái sang phải bằng các số từ 1 đến $n$.

Mỗi người lính hoặc là đã sẵn sàng thực hiện cuộc đổ bộ, hoặc là cần được huấn luyện thêm theo quy định mới. Tướng Bajtazar muốn tất cả những người lính sẵn sàng cho cuộc đổ bộ sẽ đứng thành một đoạn liên tiếp trong hàng. Nói một cách hình thức, ông muốn không tồn tại bộ ba vị trí $1 \le i < j < k \le n$ nào mà người lính ở vị trí $i$ và $k$ đều sẵn sàng, trong khi người lính ở vị trí $j$ thì không.

Vì điều kiện này có thể không được thỏa mãn mặc định, Bajtazar sẽ đưa ra $m$ mệnh lệnh. Trong mệnh lệnh thứ $i$, ông ra lệnh cho những người lính ở vị trí $a_i$ và $b_i$ trao đổi vị trí cho nhau. Những người lính sẽ đổi chỗ cho nhau khi và chỉ khi người lính ở vị trí $a_i$ sẵn sàng cho cuộc đổ bộ, còn người lính ở vị trí $b_i$ thì không.

Bajtazar đã chọn một chuỗi các mệnh lệnh và dự định sẽ thực hiện chúng. Tuy nhiên, ông không biết có bao nhiêu người lính sẵn sàng cho cuộc đổ bộ cũng như họ đang ở những vị trí nào. Vì vậy, với mỗi số nguyên $k$ từ 1 đến $n$ (bao gồm cả $n$), ông muốn giải bài toán sau: xét tất cả $\binom{n}{k}$ cấu hình ban đầu của những người lính sẵn sàng và chưa sẵn sàng, trong đó có đúng $k$ người lính sẵn sàng cho cuộc đổ bộ. Có bao nhiêu cấu hình trong số đó mà sau khi thực hiện tất cả các mệnh lệnh, điều kiện của Bajtazar được thỏa mãn (tức là những người lính sẵn sàng cho cuộc đổ bộ sẽ tạo thành một đoạn liên tiếp trong hàng)? Hãy giúp ông ấy và tính các giá trị mà ông ấy cần!

Lưu ý: Vì có nhiều lập trình viên mới bắt đầu tham gia Potyczki Algorytmiczne, chúng tôi quyết định không làm khó các bạn với những con số lớn. Do đó, chỉ cần với mỗi $k$, bạn hãy đưa ra phần dư của số lượng khả năng khi chia cho 2.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $m$ ($2 \le n \le 35; 1 \le m \le 1\,000$), lần lượt biểu thị số lượng người lính trong hàng và số lượng mệnh lệnh.

Trong $m$ dòng tiếp theo là mô tả các mệnh lệnh; dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), được mô tả trong nội dung bài toán.

Dữ liệu ra

Dòng đầu tiên và duy nhất của dữ liệu ra phải chứa $n$ số nguyên cách nhau bởi dấu cách; số thứ $k$ phải bằng phần dư khi chia cho 2 của số lượng các cấu hình ban đầu của những người lính, trong đó có đúng $k$ người lính sẵn sàng cho cuộc đổ bộ và sau khi thực hiện tất cả các mệnh lệnh, tất cả những người lính sẵn sàng sẽ tạo thành một đoạn liên tiếp trong hàng.

Ví dụ

Ví dụ 1

4 4
4 1
1 2
3 4
1 4

Ví dụ 1

0 0 1 1

Ghi chú

Giải thích ví dụ: Nếu ban đầu chỉ có một người lính sẵn sàng cho cuộc đổ bộ, thì chắc chắn người đó sẽ tạo thành một đoạn liên tiếp (gồm một phần tử) trong hàng. Tuy nhiên, không có tình huống nào mà hai người lính sẵn sàng cho cuộc đổ bộ và cuối cùng họ đứng cạnh nhau.

Xét tình huống trong đó tất cả mọi người ngoại trừ người lính thứ hai trong hàng đều sẵn sàng cho cuộc đổ bộ. Mệnh lệnh đầu tiên sẽ không ảnh hưởng đến vị trí của những người lính. Sau mệnh lệnh thứ hai, vì người lính thứ nhất trong hàng đã sẵn sàng, còn người lính thứ hai thì không, họ sẽ đổi chỗ cho nhau. Mệnh lệnh thứ ba một lần nữa sẽ không có tác dụng. Vì bây giờ người lính thứ nhất trong hàng không sẵn sàng cho cuộc đổ bộ, còn người lính thứ tư thì có, nên họ sẽ không đổi chỗ cho nhau sau mệnh lệnh cuối cùng. Cuối cùng, chỉ có người lính thứ nhất trong hàng là không sẵn sàng cho cuộc đổ bộ. Đây là cấu hình ban đầu duy nhất cho $k = 3$ kết thúc theo đúng ý muốn của Bajtazar.

Do đó, với các giá trị $k$ tiếp theo, số lượng khả năng tương ứng là dãy $[4, 0, 1, 1]$.