Trong \(M\) ngày vừa qua (\(2\le M\le 10^9\)), Bessie đã tham dự \(N\) buổi vắt sữa (\(1\le N\le 10^5\)). Tuy nhiên, cô gặp khó khăn khi nhớ lại mình đã tham dự từng buổi vào lúc nào.

Với mỗi buổi \(i=1\ldots N\), cô biết rằng buổi đó diễn ra không sớm hơn ngày \(S_i\) (\(1\le S_i\le M\)). Ngoài ra, Bessie có \(C\) ký ức (\(1\le C\le 10^5\)), mỗi ký ức được mô tả bằng một bộ ba \((a,b,x)\), trong đó cô nhớ rằng buổi \(b\) diễn ra sau buổi \(a\) ít nhất \(x\) ngày.

Hãy giúp Bessie tính ngày diễn ra sớm nhất có thể của mỗi buổi vắt sữa. Dữ liệu bảo đảm Bessie không nhớ sai; nói cách khác, tồn tại một cách gán các buổi vào những ngày trong đoạn \(1\ldots M\) sao cho mọi ràng buộc từ các ký ức của cô đều được thỏa mãn.

Phân nhóm

• Các test 2-4 thỏa mãn \(N,C\le 10^3\).
• Các test 5-10 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(C\).

Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách \(S_1,S_2,\ldots,S_N\). Mỗi số thuộc đoạn \(1\ldots M\).

Mỗi dòng trong \(C\) dòng tiếp theo chứa ba số nguyên \(a\), \(b\) và \(x\), cho biết buổi \(b\) diễn ra sau buổi \(a\) ít nhất \(x\) ngày. Trên mỗi dòng, \(a\ne b\), \(a\) và \(b\) thuộc đoạn \(1\ldots N\), còn \(x\) thuộc đoạn \(1\ldots M\).

Dữ liệu ra

In \(N\) dòng, cho biết ngày diễn ra sớm nhất có thể của mỗi buổi.

Ví dụ

4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4

1
6
3
8

Nguồn

USACO 2020 February Contest, Gold - Timeline: https://usaco.org/index.php?page=viewproblem2&cpid=1017

Tác giả: Mark Gordon.