34811번 - 붉은색 푸른색 그 사이 $i$초 그 짧은 시간

문제

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

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

• $i$를 4ドル$로 나눈 나머지가 0ドル$이면 붉은 신호등은 그대로 두고, 푸른 신호등도 그대로 둔다.
• $i$를 4ドル$로 나눈 나머지가 1ドル$이면 붉은 신호등의 색을 푸른색으로 바꾸고, 푸른 신호등은 그대로 둔다.
• $i$를 4ドル$로 나눈 나머지가 2ドル$이면 붉은 신호등의 색을 푸른색으로 바꾸고, 푸른 신호등의 색을 붉은색으로 바꾼다.
• $i$를 4ドル$로 나눈 나머지가 3ドル$이면 붉은 신호등은 그대로 두고, 푸른 신호등의 색은 붉은색으로 바꾼다.

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

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

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

입력

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

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

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

출력

총 $Q$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 질문의 답을 출력한다.

제한

노트