Ở đất nước JOI có \(N\) công ty sản xuất phích cắm điện. Mỗi công ty được cấp một mã số nguyên từ \(1\) đến \(N\). Mỗi công ty sản xuất một kiểu phích cắm cùng ổ cắm tương ứng, nhưng điều phiền phức là phích cắm và ổ cắm của mỗi công ty lại có hình dạng khác với của tất cả các công ty khác.

Luật của JOI quy định rằng ổ cắm phải được in mã công ty sản xuất, còn trên phích cắm thì không có mã công ty. Để có thể đáp ứng nhanh yêu cầu của khách hàng trong hoàn cảnh đó, chủ một cửa hàng đồ điện có một hộp dụng cụ chứa đủ \(N\) loại phích cắm có ở JOI, mỗi loại một chiếc, được xếp theo thứ tự mã công ty. Tuy nhiên, một ngày nọ, ông vô tình làm các phích cắm trong hộp bị xáo trộn. Ông có thể nhận ra rằng một loại phích cắm nào đó không cắm vừa một loại ổ cắm nào đó, nhưng không thể chỉ nhìn phích cắm mà biết công ty sản xuất. Vì vậy, ông không thể xếp lại các phích cắm như cũ. Cuối cùng, trong lúc hết sức bối rối, ông nhờ giáo sư L, người nổi tiếng có thể dễ dàng giải quyết mọi bài toán khó.

Để tiện phân biệt, giáo sư L đánh số các phích cắm đã bị xáo trộn từ \(1\) đến \(N\), rồi dựa trên cách đánh số đó thu thập \(M\) lời khẳng định từ người chủ cửa hàng. Lời khẳng định thứ \(k\) là: “Không phích cắm nào mang số từ \(C_k\) đến \(D_k\) cắm vừa bất kỳ ổ cắm nào có mã công ty từ \(A_k\) đến \(B_k\).” Các khoảng này đều bao gồm cả hai đầu mút.

Sau đó, giáo sư L nói: “Bí ẩn đã được giải quyết. Chỉ có duy nhất một cách ghép các phích cắm với công ty sản xuất thỏa mãn \(M\) lời khẳng định này. Phần còn lại ta giao cho con.” Rồi giáo sư ra về. Dù việc này thật vô lý, bạn, người học trò của giáo sư, phải giải quyết bài toán và cho chủ cửa hàng biết phích cắm nào do công ty nào sản xuất.

Yêu cầu

Hãy viết chương trình xác định sự tương ứng giữa các phích cắm và công ty sản xuất dựa trên những lời khẳng định của chủ cửa hàng.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(k\) mô tả lời khẳng định thứ \(k\), gồm bốn số nguyên \(A_k\), \(B_k\), \(C_k\), \(D_k\), cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(i\) chứa số hiệu của phích cắm do công ty có mã \(i\) sản xuất.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• \(1\le N\le 3\,000\).

• \(1\le M\le 100\,000\).
• \(1\le A_k\le B_k\le N\) và \(1\le C_k\le D_k\le N\) với mọi \(1\le k\le M\).
• Có duy nhất một cách ghép tương ứng giữa \(N\) phích cắm và \(N\) công ty thỏa mãn tất cả \(M\) lời khẳng định.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ kiểm thử có tổng cộng \(20\) điểm thỏa mãn \(N\le 100\) và \(M\le 100\).

Ví dụ

3 2
1 1 2 3
1 2 3 3

1
2
3

8 7
2 4 2 3
4 7 1 2
6 8 1 4
3 4 3 5
5 6 6 8
6 7 6 7
7 8 6 6

2
4
1
6
3
5
8
7