Hadisələrin xronologiyası#10123
Bəsi son gün ərzində sağım ziyarət edib. Lakin o, hər sağımı nə vaxt ziyarət etdiyini xatırlamaqda çətinlik çəkir.
Hər bir sağım üçün i = 1,..., n, onun s_i günündən əvvəl baş vermədiyini bilir. Bundan əlavə, Bəsinin qeydi var, hər biri (a, b, x) üçlüyü ilə təsvir olunur ki, bu da sağım -nin sağım -dan ən azı gün sonra baş verdiyini göstərir.
Bəsiyə sağımın mümkün olan ən erkən tarixlərini hesablamağa kömək edin. Bütün qeydlərin düzgün olduğu təmin edilir, yəni bütün qeydlərə cavab verən bir həll (bütün rəqəmlər intervalında) mövcuddur.
Birinci sətir n~(1 \le n \le 10^5), m~(2 \le m \le 10^9), c~(1 \le c \le 10^5) ədədlərini ehtiva edir. Növbəti sətir tam ədəd s_1, s_2,...,s_n~(1 \le s_i \le m) ehtiva edir, hər biri intervalında yerləşir.
Növbəti sətir hər biri üç tam ədəd a, b, x ehtiva edir ki, bu da sağım -nin sağım -dan ən azı gün sonra baş verdiyini göstərir. Hər sətir üçün a \ne b, a və intervalına aiddir və intervalına aiddir.
Sağımın mümkün olan ən erkən tarixlərini müəyyən edən sətir çıxarın.
İkinci sağım birinci sağımdan ən azı beş gün sonra baş verib, buna görə də o, 1 + 5 = 6-cı gündən əvvəl baş verə bilməzdi. Dördüncü sağım ikinci sağımdan ən azı iki gün sonra baş verib, buna görə də o, 6 + 2 = 8-ci gündən əvvəl baş verə bilməzdi.
Nümunə 1