시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2 1 1 100.000%

문제

상근이는 토끼 N마리를 키우고 있다. 그는 매일 매일 토끼에게 다양한 야채와 과일을 먹이로 주고 있었다. 그러나, 상근이의 토끼는 딸기를 가장 좋아한다. 하지만 겨울에는 딸기를 구하기가 매우 어렵고, 가격도 비싸다. 따라서 상근이는 일부 토끼에게만 딸기를 주기로 했다.

상근이 토끼의 이름은 숫자이고, 1번부터 N번이다. 상근이는 각 토끼가 먹는 딸기의 양을 기록을 하기 위해서 다음과 같은 방법을 이용한다.

매일 상근이는 딸기 S개를 구매한다. 그러고 난 뒤, A번 토끼에게 첫 번째 딸기를, A+1번 토끼에게 두 번째 딸기를, A+2번 토끼에게 세 번째 딸기를,.... 준다.

모든 토끼는 비어있는 성냥갑을 가지고 있고, 이 성냥갑은 한 줄로 놓여져 있다.

K·K ≤ N을 만족하는 가장 큰 K를 고른다. 그 다음 첫 성냥갑부터 K개씩 그룹을 지어준다. 각 성냥갑의 앞에는 컵을 하나씩 놓는다. 이렇게 연속하는 K개 성냥갑과 컵을 블럭이라고 한다.

토끼에게 딸기를 준 다음에, 상근이는 딸기를 받은 토끼의 성냥갑에 성냥을 넣는다. 이 때, 어떤 블럭에 모든 성냥갑에 성냥을 넣어야된다면, 성냥갑 대신에 컵에 성냥을 넣는다. 

위의 방법을 사용하면, 각 토끼가 지금까지 먹은 딸기의 수는 성냥갑과 컵에 들어있는 성냥의 수가 된다.

예를 들어, 위와 같이 토끼가 11마리 있다고하자. 그럼 N = 11이 된다. 이 때, K를 구하면 K = 3이 된다. 따라서, 총 네 개의 블럭이 있을 것이고, 마지막 블럭에는 성냥갑이 2개만 있을 것이다. 만약, 상근이가 딸기를 6개 사왔고, 5번 토끼부터 딸기를 준다면, 성냥갑과 컵에 들어있는 성냥은 아래와 같이 된다.

토끼의 수 N이 주어지고, M일동안 구마한 딸기의 수와 토끼에게 준 방법이 주어진다. 이 때, 상근이가 그날 성냥을 넣은 성냥갑과 컵에 들어있는 성냥의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 100000)

다음 M개 줄에는 각 날 상근이가 구매한 딸기의 수 S와 딸기를 주기 시작하는 토끼의 번호 A가 주어진다. (1 ≤ A ≤ N, 1 ≤ A+S–1 ≤ N)

출력

출력은 총 M개의 숫자를 출력해야 한다. k번째 줄에는 k번째 날에 성냥을 넣은 성냥갑과 컵에 들어있는 성냥의 수를 출력해야 한다.

예제 입력

11 3
6 5
3 1
11 1

예제 출력

4
1
6

힌트

예제의 경우에는 토끼가 11마리 있고, 블럭이 4개있는 경우이다. (그림과 같은 경우)

첫째 날 상근이가 딸기를 주는 토끼의 번호는 5번부터 10번이다. 성냥갑 5,6,10번에는 성냥을 넣을 것이고, 세 번째 컵에 성냥갑을 넣는다. 첫째 날이기 때문에, 원래 성냥이 들어있는 성냥갑과 컵은 없다. 따라서 정답은 4가 된다.

둘째 날 상근이는 1번부터 3번토끼에게 딸기를 준다. 첫 번째 컵에 성냥을 넣으면 된다.

셋째 날에는 모든 토끼에게 딸기를 준다. 이런 경우에는 모든 컵에 성냥을 하나씩 넣으면 된다. 따라서, 정답은 6이 된다.