배달원

어느 음식 배달 회사에 배달원 $N$명이 근무한다. 모든 배달원은 같은 시각, 즉 아침(시각 $t = 0$분)에 근무를 시작한다. 하루 동안 주문이 들어오며, 각 주문에 대해 다음 정보가 주어진다.

• 주문이 접수된 시각(분)
• 그 주문을 완료했을 때 배달원이 받는 금액
• 각 배달원이 그 주문을 완료하는 데 걸리는 시간(분). 한 주문에 대한 각 배달원의 소요 시간은 모두 서로 다르다.

주문은 그 시점에 손이 빈(다른 주문을 수행하고 있지 않은) 배달원 중에서 그 주문을 가장 빨리 완료할 수 있는 배달원에게 배정된다. 만약 그 시점에 모든 배달원이 바쁘다면, 손님은 다른 회사에 의뢰하므로 그 주문은 사라진다.

배달원은 그날 자신에게 배정된 모든 주문을 완료하면 퇴근한다.

각 배달원이 하루 동안 얼마를 버는지 계산하라.

어떤 배달원이 주문을 완료하는 시각이 새 주문의 접수 시각과 정확히 같다면, 그 배달원은 새 주문 시점에 손이 빈 것으로 간주한다.

첫째 줄에 배달원 수 $N$과 주문 수 $M$이 주어진다. 이어지는 $M$개의 줄에 각 주문의 정보가 주어진다.

• $t$ — 근무 시작 시점부터 주문이 접수된 시각(분). 모든 주문의 접수 시각은 서로 다르며, 증가하는 순서로 주어진다.
• $v$ — 그 주문을 완료했을 때 배달원이 받는 금액.
• $z_1, z_2, \dots, z_N$ — $i$번째 배달원이 이 주문을 완료하는 데 $z_i$분이 걸림을 의미한다. 한 주문에 대한 값들은 모두 서로 다르다.

한 줄에 $N$개의 정수를 출력한다. $i$번째 수는 $i$번째 배달원이 그날 번 금액이다.

• $1 \le N \le 100$
• $1 \le M \le 1000$
• $1 \le t_1 < t_2 < \dots < t_M \le 1000$
• $1 \le v_i \le 1000$
• $1 \le z_i \le 100$