Hadisələrin xronologiyası

Bəsi son $m$ gün ərzində $n$ 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 $c$ qeydi var, hər biri $(a,b,x)$ üçlüyü ilə təsvir olunur ki, bu da sağım $b$-nin sağım $a$-dan ən azı $x$ 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 $[1,m]$ intervalında) mövcuddur.

Giriş verilənləri

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 $n$ tam ədəd $s_1,s_2,...,s_n(1\le s_i\le m)$ ehtiva edir, hər biri $[1,m]$ intervalında yerləşir.

Növbəti $c$ sətir hər biri üç tam ədəd $a,b,x$ ehtiva edir ki, bu da sağım $b$-nin sağım $a$-dan ən azı $x$ gün sonra baş verdiyini göstərir. Hər sətir üçün $a\ne b,a$ və $b$ $[1,n]$ intervalına aiddir və $x$ $[1,m]$ intervalına aiddir.

Çıxış verilənləri

Sağımın mümkün olan ən erkən tarixlərini müəyyən edən $n$ sətir çıxarın.

Nümunələr

İ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.