Karjeras

Sklype atrasta naudingųjų iškasenų. Planuojama sklype sumontuoti naują automatinę kasimo sistemą, ją naudoti ir sklypą paversti naudingųjų iškasenų karjeru.

Ši sistema gali vienu metu iškasti viso karjero pločio duobę, kurios pradžia yra Si, pabaiga – Ei metrų nuo karjero pradžios, o gylis – Hi metrų.

Sklypą (karjerą) galima pavaizduoti kaip dvimatį brėžinį, kuris vaizduoja karjero aukštį virš jūros lygio išilgai karjero, tiek pradiniu momentu, tiek vėliau, pradėjus naudingųjų iškasenų kasimą.

Automatinė kasimo sistema dirba vykdydama kasimo komandas. Kiekviena komanda sumažins karjero aukštį Hi metrų nurodytame intervale. 1 pav. parodyta, kaip keičiasi karjero aukštis įvykdžius dvi komandas, kurių pirma kasa intervale [0; 2], antra – [1; 3], abi iškasa 1 metro gylio duobes. Komandų iškasami plotai atitinkamai pažymėti žaliai (atspausdintoje nespalvotoje sąlygoje – šviesiai pilkai) ir mėlynai (nespalvotoje sąlygoje – pilkai).

1 pav.

Karjero savininkas žino, kokias kasimo komandas duos šiai sistemai, bet prieš pradėdamas nori sužinoti, kaip atrodys karjeras įvykdžius visas komandas.

Suraskite karjero aukštį įvykdžius visas kasimo komandas.

Pirmoje eilutėje pateikiami du sveikieji skaičiai: karjero ilgis N ir komandų skaičius K.

Antroje eilutėje pateikiama N sveikųjų skaičių Ai – pradinis karjero aukštis virš jūros lygio i metrų nuo karjero pradžios. Pirmoji reikšmė nurodo aukštį 0 metrų nuo karjero pradžios.

Toliau pateikiama K eilučių, kuriose yra po tris sveikuosius skaičius: i-tosios kasimo komandos pradžia Si, pabaiga Ei ir gylis Hi.

Išveskite N skaičių, kurių i-tasis nurodytų, koks būtų karjero aukštis i metrų nuo karjero pradžios įvykdžius visas komandas.

Galutinis aukštis gali būti neigiamas.

• 0 ≤ Si ≤ Ei < N ≤ 250 000
• 1 ≤ K ≤ 250 000
• -1 000 ≤ Ai, Hi ≤ 1 000