알파카 왕국에는 길이 \(N\)의 거대한 도로가 있다.

알파카 왕국의 왕 경현이는 이 도로에 조명을 설치하려 한다. 위치 \(X\)에 밝기 \(L\)의 조명을 설치하면, 그곳에서 거리 \(d\)만큼 떨어진 지점의 밝기에 \(\max(0,\ L-d)\)만큼이 더해진다.

예를 들어 \(N = 5\)이고 도로 각 지점의 밝기가 \(0\ 1\ 1\ 0\ 0\)일 때, 위치 \(3\)에 밝기 \(2\)의 조명을 설치하면 각 지점의 밝기는 \(0\ 2\ 3\ 1\ 0\)이 된다.

현재 모든 지점의 밝기는 \(0\)이다. 경현이는 총 \(M\)개의 조명을 설치할 계획이며, \(i\)번째 조명의 위치는 \(X_i\), 밝기는 \(L_i\)이다.

\(M\)개의 조명을 모두 설치했을 때 각 지점의 밝기를 계산하는 프로그램을 작성하시오.

• \(1 \le N, M \le 1{,}000{,}000\)

• \(1 \le X_i, L_i \le N\)

• 모든 입력값은 정수이다.

첫째 줄에 정수 \(N\)과 \(M\)이 주어진다.

둘째 줄부터 \(M\)개의 줄에 두 정수 \(X_i\), \(L_i\)가 주어진다.

\(1\)번부터 \(N\)번까지 각 지점의 최종 밝기를 공백으로 구분하여 출력한다.

pythonprominhyeong 작성

출처 @pythonprominhyeong