Танд a1, a2, ..., aN гэсэн бүхэл тоон жингүүдтэй дараалсан N ширхэг туухай өгөгдсөн. Олонлог эгзэ сургуулийн зүгээс танд q ширхэг даалгавар өгөх бөгөөд даалгавар тус бүр нь жагсаалт дахь тодорхой завсарт орших тоонуудын нийлбэрийг олж өгөх даалгавар өгөх юм. Өөрөөр хэлбэл индексийн хувьд [i, j] завсарт i-р туухайнаас j-р туухайг дуустал бүх туухайнуудын жингийн нийлбэрийг олж хэвлээд байх явдал юм.

Оролт:

Оролтын файлын эхний мөрөнд туухайнуудын тоо болох N бүхэл тоо, даалгаврын тоо болох Q тоо өгөгдөнө.

Дараагийн мөрөнд туухайнуудын жин болох a1, a2, ..., aN гэсэн бүхэл тоонууд хоосон зайгаар тусгаарлагдан нэг мөрөнд өгөгдөнө.

Дараагийн Q ш мөрөнд даалгавр тус бүрийн завсрыг илэрхийлэх i, j тоонууд хоосон зайгаар тусгаарлагдан мөр бүрд өгөгдөнө.

Гаралт:

Гаралтын файлын Q ш мөрөнд мөр тус бүрд даалгаварт өгөгдсөн [i,j] завсар дахь элементүүдийн нийлбэр болон нэг бүхэл тоонуудыг хэвлэх явдал юм.

Хязгаарлалтууд:

• \(1 <= n,q <= 2 * 10^5\)
• \(1 <= ai <= 10^9\)
• \(1 <= i < j <= n\)

Жишээ:

Оролт-1

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

Гаралт-1

11
2
24
4