Mảng thú vị (Interesting Array)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Tìm một mảng số nguyên không âm sao cho AND bit trên từng đoạn ràng buộc bằng đúng giá trị được cho, hoặc kết luận không tồn tại.

Input

Dòng đầu chứa $n,m$. Mỗi trong $m$ dòng tiếp theo chứa $l_i,r_i,q_i$, yêu cầu $a_{l_i}\mathbin{\&}a_{l_i+1}\mathbin{\&}\cdots\mathbin{\&}a_{r_i}=q_i$.

Output

Nếu không tồn tại mảng, in NO. Nếu tồn tại, in YES rồi một dòng gồm $n$ số $a_i$ thỏa mọi ràng buộc. Có thể có nhiều đáp án đúng; bài dùng special checker.

Subtask

• 20 điểm: $n,m\le50$.
• 30 điểm: $n,m\le5000$.
• 50 điểm: $n,m\le10^5$, $0\le q_i<2^{30}$, $0\le a_i<2^{30}$.

Ví dụ

Input

3 1
1 3 3

Output

YES
3 3 3

Giải thích

Ràng buộc yêu cầu AND của cả ba phần tử bằng 3. Mảng 3 3 3 thỏa vì $3\mathbin{\&}3\mathbin{\&}3=3$. Nhiều mảng khác cũng có thể hợp lệ.