붉은색 푸른색 그 사이 ii초 그 짧은 시간

시간 제한3초메모리 제한1024 MB

요약
N명의 사람이 정해진 규칙에 따라 신호등을 바꾼 뒤, Q개의 구간에 있는 푸른 신호등의 개수를 구한다.
난이도

어려움10점 중 8점

유형
정수론, 수학, 누적 합, 구현
정답자
아직 제출이 없습니다

문제

수직선 형태의 길거리에 1≤i≤N1\le i\le N을 만족하는 모든 정수 ii에 대해 위치 ii에는 ii번 신호등이 위치해 있다. 이 신호등은 처음엔 모두 붉은색으로 표시되어 있다.

오늘은 신호등 점검일이다. 1,2,⋯ ,N1, 2, \cdots, N번의 사람이 순서대로 각 신호등을 점검한다. ii번 사람은 위치 00에서 ii초에 출발하며, 매초 11의 속도로 양의 방향으로 이동한다. 이동을 시작한 뒤, 매 ii초가 지날 때마다 자신이 위치한 지점의 신호등에 다음 동작을 수행한다:

  • ii를 44로 나눈 나머지가 00이면 붉은 신호등은 그대로 두고, 푸른 신호등도 그대로 둔다.
  • ii를 44로 나눈 나머지가 11이면 붉은 신호등의 색을 푸른색으로 바꾸고, 푸른 신호등은 그대로 둔다.
  • ii를 44로 나눈 나머지가 22이면 붉은 신호등의 색을 푸른색으로 바꾸고, 푸른 신호등의 색을 붉은색으로 바꾼다.
  • ii를 44로 나눈 나머지가 33이면 붉은 신호등은 그대로 두고, 푸른 신호등의 색은 붉은색으로 바꾼다.

이때, 모그는 모든 사람이 순회한 후 특정 구간에 푸른 신호등이 몇 개가 있는지 궁금해졌다. 따라서 QQ번의 질문을 하기로 했다.

  • l,rl\\, r: 번호가 ll 이상 rr 이하인 신호등 중 푸른 신호등의 개수를 구한다.

모그의 질문에 대신 답해주도록 하자.

입력

첫째 줄에 양의 정수 NN이 주어진다. (1≤N≤1012)(1\le N\le 10^{12})

둘째 줄에 양의 정수 QQ가 주어진다. (1≤Q≤100)(1\le Q\le 100)

셋째 줄부터 QQ개의 줄에 걸쳐 양의 정수 l,rl, r이 공백으로 구분되어 주어진다. (1≤l≤r≤N)(1\le l\le r\le N)

출력

총 QQ개의 줄에 걸쳐 답을 출력한다. ii번째 줄에는 ii번째 질문의 답을 출력한다.

예제1

  1. 예제 1

    입력
    5
3
1 3
2 4
1 5
    예상 출력
    1
0
2