Dòng thời gian

Có $N$ sự kiện. Sự kiện $i$ xảy ra không sớm hơn ngày $S_i$. Có $C$ ràng buộc: sự kiện $b$ xảy ra ít nhất $x$ ngày sau sự kiện $a$. Tìm ngày sớm nhất có thể cho mỗi sự kiện.

Dữ liệu vào

• Dòng đầu: $N$, $M$, $C$.
• Dòng thứ hai: $N$ số $S_i$.
• $C$ dòng tiếp: $a$, $b$, $x$.

Dữ liệu ra

• $N$ dòng, ngày sớm nhất mỗi sự kiện.

Ràng buộc

• $1\le N,C\le {10}^5$, $2\le M\le {10}^9$

Ví dụ