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:
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ử \(a_1, a_2, ...,a_n\) và \(m\) truy vấn mỗi truy vấn có là hai giá trị \(L, R\) \((1 \leq L \leq R \leq 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à \(a_L+a_{L+1}+...+a_R\).

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 \leq n,m \leq 10^5)\).

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á \(10^6\).

Các dòng cuối gồm \(m\) dòng mỗi dòng chứa hai số dương \(L, R\) \((1 \leq L \leq R \leq 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

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

Output

22
17
5

Comments


  • 1
    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é