Hôm nay Anh Mạnh iu dấu sẽ chỉ các bé về mảng cộng dồn nha, Anh Mạnh có một mảng ~A~ có ~N~ số nguyên và hãy trả lời anh Mạnh ~Q~ câu hỏi mà anh Mạnh đã đề ra là đố bạn tổng các số từ phần tử thứ ~L~ tới phần tử thứ ~R~ là bao nhiêu ~( a_l, a_{l+1}, ..., a_{r-1}, a_r )~

Input

• Một số nguyên duy nhất là ~T (1 \leq T \leq 5)~ testcase và ~T~ khối tiếp theo gồm:
  • Hai số nguyên là ~N, Q(1 \leq N, Q \leq 10^5)~, đại diện cho số phần tử của mảng ~A~ và số truy vấn
  • Dòng tiếp theo gồm các phần tử ~a_i( 1 \leq i \leq N, 1 \leq a_i \leq 10^9 )~ của mảng ~A~.
  • Và ~Q~ dòng tiếp theo gồm 2 số nguyên ~L, R( 1 \leq L \leq R \leq N,)~, đại diện cho truy vấn từ ~L~ tới ~R~

Output

• Mỗi dòng in ra câu trả lời của mỗi truy vấn

Sample Input

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

Sample Output

5
6
5