Truy vấn tổng đoạn con liên tiếp

Submit solution
Points: 2 (partial)
Time limit: 1.0s
JAVA11 2.0s
Python 3 2.0s
Memory limit: 977M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho dãy số nguyên có n phần tử a1,a2,...,an và m truy vấn mỗi truy vấn có là hai giá trị L,R (1≤L≤R≤n) cần phải trả lời tổng của dãy con liên tục từ vị trí L đến vị trí R là aL+aL+1+...+aR.

Input

Dòng đầu gồm hai số nguyên dương n và m tương ứng với số phần tử của dãy và số lần truy vấn (1≤n,m≤105).

Dòng tiếp theo gồm n số nguyên là các phần tử của dãy có giá trị tuyệt đối không vượt quá 106.

Các dòng cuối gồm m dòng mỗi dòng chứa hai số dương L,R (1≤L≤R≤n).

Output

Xuất ra m dòng mỗi dòng là tổng của dãy con liên tục từ vị trí L đến R.

Ví dụ

Input

Copy
6 3
4 7 2 8 1 -6
1 5
2 4
3 6

Output

Copy
22
17
5

Comments


  • 2
    TICHPX  commented on Oct. 31, 2019, 12:47 p.m.

    Nhớ dùng scanf và printf thay cho cin và cout để tránh TLE nhé