Hai hồ nước được nối bởi \(n\) kênh. Mỗi kênh có hai cổng và chỉ mở khi cả hai cổng đều mở. Các cổng được điều khiển bởi \(m\) công tắc: một công tắc có thể điều khiển nhiều cổng, nhưng mỗi cổng do đúng một công tắc điều khiển. Hai cổng của cùng một kênh có thể dùng chung công tắc; cũng có thể có công tắc không điều khiển cổng nào.

Mỗi cổng hoạt động theo một trong hai chế độ:

• cổng mở khi công tắc bật và đóng khi công tắc tắt;
• cổng đóng khi công tắc bật và mở khi công tắc tắt.

Hãy xác định liệu có thể đặt trạng thái các công tắc sao cho mọi kênh đều đóng hay không. Nếu có, hãy tìm một cấu hình như vậy.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n\) và \(m\) — số kênh và số công tắc (\(1\le n\le 250\,000\), \(1\le m\le 500\,000\)). Các công tắc được đánh số từ \(1\) đến \(m\).

Mỗi trong \(n\) dòng tiếp theo chứa bốn số nguyên \(a,s_a,b,s_b\). Hai cổng của kênh lần lượt do công tắc \(a\) và \(b\) điều khiển (\(1\le a,b\le m\)). Mỗi giá trị \(s_a,s_b\) bằng 0 hoặc 1; \(s_i=0\) nghĩa là cổng đóng khi và chỉ khi công tắc \(i\) tắt, còn \(s_i=1\) nghĩa là cổng đóng khi và chỉ khi công tắc \(i\) bật.

Dữ liệu ra

Nếu có thể đóng tất cả các kênh, in \(m\) dòng. Dòng thứ \(i\) chứa 0 nếu công tắc \(i\) cần tắt, hoặc 1 nếu cần bật. Nếu có nhiều cấu hình hợp lệ, có thể in bất kỳ cấu hình nào.

Nếu không thể, in một dòng duy nhất chứa IMPOSSIBLE.

Phân nhóm

1. Ít nhất 30 điểm: \(n\le 40\) và \(m\le 20\).
2. Các test còn lại: không có ràng buộc bổ sung.

Ví dụ

3 2
1 0 2 1
1 0 2 0
1 1 2 1

0
1

2 1
1 0 1 0
1 1 1 1

IMPOSSIBLE