Cho dãy gồm \(n\) số nguyên \(a_1,a_2,\ldots,a_n\). Thực hiện \(Q\) truy vấn, mỗi truy vấn có dạng hai số nguyên dương \(L,R\) với yêu cầu tính:

Input

• Dòng đầu chứa hai số nguyên dương \(n,Q\) \((1 \leq n,Q \leq 2 \times 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\)
• Tiếp theo là \(Q\) dòng, mỗi dòng chứa hai số nguyên \(L, R\) thể hiện một truy vấn \((1 \leq L \leq R \leq n)\)

Output

• Với mỗi truy vấn, in một số nguyên là kết quả tìm được trên một dòng

Example

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

2
1
1
4