Có thể bạn đã biết rồi.
Nhưng 100g bánh chưng sẽ cung cấp năng lượng khoảng 181kcal 😨

Tuy thế nhưng Đạt vẫn rất thích ăn bánh chưng, đơn giản vì bánh chưng nhà Đạt làm quá ngon 😋
Thế nên Đạt đã ghi lại số bữa mình ăn bánh chưng và số miếng bánh chưng Đạt ăn mỗi bữa.
Đạt có một phương pháp để lên kế hoạch giảm cân đặc biệt hiệu quả tuy nhiên trước tiên Đạt cần biết tổng số miếng bánh chưng đã ăn từ bữa thứ i đến bữa thứ j
Hãy giúp Đạt trả lời những câu hỏi để Đạt có thể lên kế hoạch giảm cân nhé.

Đầu vào

• Một dòng đầu tiên gồm hai số nguyên dương:
  • n - Số bữa ăn Đạt đã ghi lại (1 ≤ n ≤ 10⁵)
  • q - Số câu hỏi Đạt cần bạn trả lời (1 ≤ n ≤ 10⁵)
• Dòng tiếp theo chứa n số nguyên dương a₁, a₂, ... , a_n - Số miếng bánh chưng Đạt ăn mỗi bữa
• q dòng tiếp theo, mỗi dòng là câu hỏi của Đạt gồm 2 số nguyên dương: Số miếng bánh chưng ăn từ bữa thứ i tới bữa thứ j (1 ≤ i ≤ j ≤ n)

Đầu ra

q dòng, mỗi dòng chứa duy nhất một số nguyên - tổng số miếng bánh chưng Đạt đã ăn từ bữa thứ i tới bữa thứ j

Example Input

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

Example Output

1
3
5
9
15