시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB21141263.158%

문제

Greitai Kalėdos. Elniai jau pakinkyti ir Kalėdų senelis beveik pasiruošęs traukti į kelionę, tik dovanos dar nesukrautos.

Nors rogėse telpa be galo daug dovanų, bet sunkias roges tempiantis kinkinys greitai pavargsta, todėl dovanų reikia krauti kiek galima mažiau.

Tai žinodami nykštukai Kalėdų senelio mašrute ant namų stogų įrengė dovanų slėptuves.

Kalėdų senelis gali pasikrauti dovanų savo trobelėje (t.y. pradiniame taške), o taip pat bet kurioje slėptuvėje.

Žinodami, kiek vaikų turi aplankyti Kalėdų senelis, patarkite, kiek dovanų jam reikia įkrauti į roges savo trobelėje bei kiekvienoje slėptuvėje, kad jų kiekis rogėse visada būtų kuo mažesnis.

Keliaudamas Kalėdų senelis:

  • lanko vaikus namų numerių didėjimo tvarka, pradėdamas nuo pirmojo;
  • negali apgręžti rogių atgal iki neaplanko visų vaikų;
  • jei ant namo stogo yra įrengta slėptuvė, jis pirma joje pasipildo roges dovanų, o tuomet neša dovaną tame name gyvenančiam vaikui.

Visi vaikai gyvena skirtinguose namuose ir kiekvienam jų atneš vieną dovaną.

입력

Pirmojoje eilutėje pateikti du sveikieji skaičiai:

  • $N$ – vaikų skaičius;
  • $M$ – dovanų slėptuvių skaičius.

Kitose $M$ eilučių pateikta po du skaičius:

  • $K_i$ – ant kelinto vaiko namo stogo įrengta slėptuvė. Duomenys pateikti $K_i$ didėjimo tvarka;
  • $Z_i$ – dovanų skaičius šiame sandėlyje.

Pradiniame taške yra Kalėdų senelio trobelė, joje yra be galo daug dovanų.

출력

Išveskite $M + 1$ skaičių skirtingose eilutėse. Pirmojoje eilutėje nurodykite, kiek dovanų reikia įsidėti prieš pradedant kelionę. Kitose $M$ eilučių išveskite, kiek dovanų reikia pasikrauti kiekvienoje slėptuvėje (rezultatai pateikiami ta tvarka, kokia slėptuvės pateiktos pradiniuose duomenyse).

제한

  • $1 ≤ N ≤ 10\,000$
  • $0 ≤ M ≤ N$
  • $1 ≤ K_1 < \dots < K_i < K_{i+1} < \dots < K_M ≤ N$
  • $1 ≤ Z_i ≤ 10\,000$

예제 입력 1

4 1
4 2

예제 출력 1

3
1

Prieš iškeliaujant reikia dovanų pasiimti pirmam, antram ir trečiam vaikams. Ketvirtam vaikui dovana yra ant jo namo stogo esančioje slėptuvėje.

예제 입력 2

5 2
2 1
5 100

예제 출력 2

3
1
1

Iškeliaudamas Kalėdų senelis turi įsimesti tris dovanas. Iš ant antrojo vaiko namo stogo esančios slėptuvės paimamos visos ten sukrautos dovanos. Nors paskutinėje slėptuvėje yra daug dovanų, apsimoka pasiimti tik vieną, nes ji yra ant paskutinio vaikas namo stogo.