도서관은 매일의 대출 권수를 기록해 두었어요. 사서는 "\(l\)일째부터 \(r\)일째까지 모두 몇 권이 대출됐는지" 같은 질문을 자주 합니다.

미리 누적 합을 만들어 두면 각 질문에 빠르게 답할 수 있어요. \(N\)일치 기록과 \(Q\)개의 질의가 주어질 때 각 질의 \([l, r]\) 구간의 합을 출력하세요.

입력과 질의가 매우 많을 수 있으니 빠른 입출력을 사용하세요.

• \(1 \le N, Q \le 100{,}000\)
• 각 값은 \(-100\) 이상 \(1{,}000\) 이하의 정수
• \(1 \le l \le r \le N\)

첫째 줄에 일수 \(N\)과 질의 수 \(Q\)가 주어집니다.

둘째 줄에 \(N\)개의 정수가 공백으로 구분되어 주어집니다.

다음 \(Q\)개의 줄에 각각 두 정수 \(l\), \(r\)이 주어집니다.

각 질의에 대해 구간 \([l, r]\)의 합을 한 줄에 하나씩 출력합니다.

riseoj 작성

출처 Original