To read the problem statement in English, choose the language using the flag on the navigation bar.

Trong nông trại của bác nông dân John có ~m~ cây táo. Hiện tại cũng đã đến mùa thu hoạch táo. Trước đây lực lượng lao động chính trong việc thu hoạch táo trong nông trại của bác nông dân John chính là bò Bessie và bạn của cô. Nhưng John cũng nhận thấy rằng sử dụng bò để thu hoạch táo có chi phí rất cao (chi phí nuôi bò là không thấp), nhưng lượng táo thu về có phần hao hụt (những chú bò đã ăn vụng táo??!?).

Để giảm chi phí trong công đoạn thu hoạch, cũng như gia tăng tự động hóa cho nông trại, bác nông dân John quyết định đầu tư chi phí để mua ~n~ con robot, được đánh số từ ~1~ đến ~n~. Những con robot mà bác nông dân John sẽ mua đều rất linh hoạt trong quá trình hái táo, cũng như di chuyển táo về kho. Chỉ có một tham số duy nhất của những con robot ảnh hưởng đến quá trình thu hoạch, đó chính là độ cao: chỉ có những con robot có độ cao vừa tầm cây sẽ được sử dụng để hái táo, trong khi đó những con robot thấp hơn, nhưng vừa tầm, sẽ đứng phía dưới hứng táo và di chuyển táo về kho.

Trước khi mua robot, bác nông dân John đã lên kế hoạch hái táo cho từng cây. Với cây thứ ~i~ (~1 \le i \le m~), bác nông dân sẽ chọn hai con robot có số thứ tự là ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~). Bác muốn rằng con robot cao hơn cần có độ cao là ~y_i~ để hái táo, và con robot thấp hơn cần có độ cao là ~x_i~ để hứng và di chuyển táo về kho (~x_i \le y_i~). Đó là kế hoạch của bác nông dân John, tuy nhiên bác cũng chưa biết chính xác độ cao của từng con robot mà mình sẽ mua như thế nào.

Tuy bò Bessie sẽ không làm nhiệm vụ thu hoạch táo nữa, nhưng bây giờ bò Bessie sẽ giúp bác nông dân John làm nhiệm vụ mua các con robot này và bào trì chúng. Cho biết kế hoạch hái táo của bác John, hãy giúp bò Bessie tìm ra độ cao của ~n~ con robot cần mua thỏa mãn kế hoạch của bác nông dân John. Nếu như có nhiều đáp án thỏa mãn, hãy giúp bò Bessie tìm ra đáp án bất kì. Nếu như không có đáp án nào thỏa mãn cả, bạn cũng cần thông báo cho bò Bessie biết để bò Bessie thuyết phục lại bác nông dân trao lại công việc cũ cho mình.

Input

Dòng đầ tiên chứa hai số nguyên ~n~ và ~m~ (~2 \le n \le 10^5~, ~1 \le m \le 10^5~), lần lượt là số lượng robot mà bác nông dân John dự định mua, và số lượng cây táo trong nông trại.

Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ~4~ số nguyên dương ~u_i~, ~v_i~, ~x_i~ và ~y_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~, ~1 \le x_i \le y_i \le 10^9~) thể hiện kế hoạch hái táo cho cây thứ ~i~.

Output

Nếu không thể mua ~n~ con robot thỏa mãn kế hoạch của bác nông dân John, hãy in ra ~-1~.

Ngược lại, hãy in ra ~n~ số nguyên, số thứ ~i~ trong đó là độ cao của con robot thứ ~i~. Độ cao của mỗi con robot được in ra cần không dưới ~1~ và không quá ~10^9~. Nếu có nhiều đáp án, hãy in ra đáp án bất kì.

Scoring

• Subtask 1, tương ứng với ~15~ điểm, có ~n = 2~ và ~m = 1~.

• Subtask 2, tương ứng với ~30~ điểm, có ~n \le 6~.

• Subtask 3, tương ứng với ~45~ điểm, có ~n \le 16~.

• Subtask 4, tương ứng với ~60~, không có ràng buộc gì thêm.

Tổng cộng bài toán có ~150~ điểm.

Sample Input 1

2 1
1 2 3 4

Sample Output 1

3 4

Sample Input 2

6 3
1 3 2 3
3 5 1 3
5 1 1 2

Sample Output 2

2 2 3 3 1 1

Sample Input 3

3 2
1 2 1 1
2 3 2 2

Sample Output 3

-1

Notes

Để thuật tiện trong quá trình giải thích, ta gọi ~h_i~ là độ cao của con robot thứ ~i~.

Trong ví dụ đầu tiên, trong vườn có ~m = 1~ cây táo. Bác nông dân muốn rằng cây táo này sẽ được thu hoạch bởi con robot ~1~ và ~2~, trong đó con robot cao hơn cần có độ cao là ~4~ để hái táo, và con robot thấp hơn cần có độ cao là ~3~ để hứng táo và mang táo về kho. Vì vai trò của hai con robot là như nhau, nên ngoài cách mua robot với ~h_1 = 3~ và ~h_2 = 4~, ta cũng có cách mua khác là ~h_1 = 4~ và ~h_2 = 3~.

Trong ví dụ thứ hai, tuy bác nông dân John muốn mua ~n = 6~ con robot để thu hoạch ~m = 3~ cây táo, tuy nhiên chỉ có con robot ~1~, ~3~ và ~5~ được sử dụng và có duy nhất một cách mua thỏa mãn là ~h_1 = 2~, ~h_3 = 3~ và ~h_5 = 1~. Các con robot ~2~, ~4~ và ~6~ có thể có độ cao bất kì và có thể được sử dụng cho mục đích khác (ví dụ như thay thế các con robot kia trong trường hợp hỏng hóc).

Trong ví dụ thứ ba:

• robot ~1~ và ~2~ được sử dụng để hai cây táo thứ nhất, và chúng cần có độ cao bằng nhau và bằng ~1~,

• robot ~2~ và ~3~ được sử dụng để hai cây táo thứ hai, và chúng cần có độ cao bằng nhau và bằng ~2~.

Robot ~2~ không thể vừa có độ cao ~1~ và ~2~ được, nên không có cách mua robot nào thỏa mãn kế hoạch của bác nông dân John.