토끼

농장에는 1번부터 N번까지 번호가 붙은 토끼 N마리가 있다. 농장 주인은 매일 딸기 몇 개를 사서 연속한 번호의 토끼들에게 한 개씩 준다.

각 토끼가 지금까지 먹은 딸기의 수를 기록하기 위해, 모든 토끼에게 빈 성냥갑이 하나씩 있다. 성냥갑은 한 줄로 놓여 있다. K^2 <= N을 만족하는 가장 큰 정수 K를 고른다. 첫 번째 성냥갑부터 차례대로 연속한 K개씩 묶어 블록을 만든다. 마지막 블록은 성냥갑이 K개보다 적을 수 있다. 각 블록 앞에는 컵이 하나 놓여 있다.

어느 날 딸기 S개를 사고 A번 토끼부터 나누어 주면, A번, A+1번, ..., A+S-1번 토끼가 각각 딸기 한 개를 받는다.

딸기를 준 뒤에는 다음 방식으로 성냥을 하나씩 기록한다.

• 어떤 블록의 모든 성냥갑이 그날 딸기를 받은 토끼에 해당하면, 그 블록의 컵에 성냥을 하나 넣는다.
• 그렇지 않으면, 그 블록 안에서 딸기를 받은 각 토끼의 성냥갑에 성냥을 하나씩 넣는다.

각 토끼가 지금까지 먹은 딸기의 수는 자기 성냥갑에 들어 있는 성냥 수와 자신이 속한 블록의 컵에 들어 있는 성냥 수의 합으로 알 수 있다.

아래 그림은 블록의 배치와 한 번의 기록 과정을 보여 준다.

토끼의 수 N과 M일 동안의 딸기 배분 방법이 주어진다. 각 날마다, 그날 성냥을 넣은 모든 성냥갑과 컵에 현재 들어 있는 성냥 수의 합을 구하시오.

첫째 줄에 N과 M이 공백으로 구분되어 주어진다.

• 1 <= N, M <= 100000

다음 M개 줄에는 그날 산 딸기의 수 S와 딸기를 주기 시작하는 토끼의 번호 A가 주어진다.

• 1 <= A <= N
• 1 <= A+S-1 <= N

M개의 수를 출력한다. k번째 줄에는 k번째 날에 성냥을 넣은 성냥갑과 컵에 현재 들어 있는 성냥 수의 합을 출력한다.

어떤 블록이 완전히 포함되려면 그 블록 안의 모든 성냥갑이 그날의 토끼 범위에 들어 있어야 한다. 마지막 블록은 K개보다 짧을 수 있으며, 그 안의 모든 성냥갑이 포함되면 완전히 포함된 것으로 처리한다.