Cho mảng ~A~ gồm ~N~ phần tử, giá trị của một đoạn ~(l, r)~ trong mảng là tổng của các cặp ~A_i \times A_j~ với ~l~ ~\le~ ~i~ ~<~ ~j~ ~\le~ ~r~ .

Cho ~Q~ truy vấn, hãy tính và in ra từng giá trị.

Dữ liệu

Dòng đầu tiên chứa hai số ~N, Q~ (~N , Q~ ~\le~ ~10^5~) . Dòng tiếp theo gồm ~N~ số nguyên dương (~A_{i}~ ~\le~ ~5 \times 10^4~). Tiếp theo là gồm ~Q~ dòng, mỗi dòng gồm hai số nguyên dương ~l, r~ (~1~ ~\le~ ~l~ ~<~ ~r~ ~\le~ ~N~).

Kết quả

In ra ~Q~ dòng, mỗi dòng là giá trị đoạn ~(l, r)~ ở truy vấn đấy .

Test ví dụ

Dữ liệu

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

Kết quả

2
11
6