Bitlandijos maisto pristatymo įmonėje „Unter Valgyt” dirba N kurjerių. Visi kurjeriai pradeda darbą tuo pačiu laiku – ryte (Bitlandijos laiku t = 0 minučių). Dienos metu gaunami užsakymai, apie kiekvieną kurių yra žinoma:</p>

• Užsakymo gavimo laikas (minutėmis);
• Vertė, kiek kurjeris uždirbs už jo įvykdymą;
• Laikus, kiek užtruktų kiekvienas kurjeris įvykdyti užsakymą (minutėmis). To paties užsakymo įvykdymo laikai yra skirtingi visiems kurjeriams.

Užsakymas yra priskiriamas laisvam kurjeriui (tuo metu nevykdančiam jokio užsakymo), kuris jį įvykdytų greičiausiai. Jei tuo metu visi kurjeriai yra užimti, užsakymas dingsta, nes klientas kreipiasi į kitą įmonę.

Kurjeriai baigia dirbti, kai įvykdo visus per dieną gautus užsakymus.

Suskaičiuokite, kiek kiekvienas kurjeris uždirbs per dieną.

입력 형식

Pirmoje eilutėje yra pateikti du skaičiai: kurjerių (N) ir užsakymų (M) skaičius. Kitose M eilučių duota užsakymų informacija:</p>

• t – užsakymo gavimo laikas minutėmis nuo darbo dienos pradžios. Visų užsakymų laikai yra skirtingi ir pateikti didėjimo tvarka.
• v – užsakymo vertė, kurią kurjeris uždirbs jį įvykdęs.
• z₁, z₂, z₃, ...z_n – laikai, kurie reiškia, kad i-asis kurjeris įvykdyti šį užsakymą užtruks z_i minučių. Visi vieno užsakymo laikai yra skirtingi.

Vienoje eilutėje pateikite N skaičių – kiek uždirbs kiekvienas kurjeris tą dieną.

예제 입력 1

3 3
1 2 3 1 2
2 3 5 3 4
4 6 5 3 4

예제 출력 1

0 5 6

예제 입력 2

2 3
1 11 7 5
2 94 9 5
4 555 11 16

예제 출력 2

94 11