Trong ngày trao thưởng cho các lập trình viên nhí, ban tổ chức đã chuẩn bị trước rất nhiều món quà trong đó có ~ n ~ món quà (được đánh số từ 1 đến ~ n ~ ) được bày sẵn trên sân khấu, món quà thứ ~ i ~ có giá trị ~ a_i ~ ~ (1 ≤ a_i ≤ 10^6; i = 1..n) ~.

Có ~ m ~ lập trình viên nhí được nhận quà trong đợt này, các lập trình viên được đánh số từ 1 đến ~ m ~. Ban tổ chức gọi lần lượt từng người lên nhận quà, người thứ ~ i ~ được nhận món quà có số thứ tự từ ~ l_i ~ đến ~ r_i ~ ~ ( 1 ≤ l_i ≤ r_i ≤ n ) ~. Khi người thứ ~ i ~ nhận quà xong, các vị trí từ ~ l_i ~ đến ~ r_i ~ sẽ được bổ sung các món quà khác có cùng giá trị.

Giả sử một lập trình viên nhận các món quà có giá trị ~ b_1, b_2, …, b_k ~, khi gộp các món quà lại thì giá trị món quà mà người này nhận được là ~ s_1^2 × 1 + s_2^2 × 2 + s_3^2 × 3 + ⋯+ s_{10^6}^2 × 10^6 ~, trong đó ~ s_i ~ ~ ( i = 1...10^6) ~ là số lần xuất hiện của ~ i ~ trong ~ b_1, b_2, …, b_k ~.

Ví dụ một lập trình viên nhận được các món quà có giá trị ~ 1, 2, 3, 1, 1, 3 ~; sau khi gộp lại có: 3 món quà giá trị 1, 1 món quà giá trị 2 và 2 món quà giá trị 3. Vậy giá trị món quà người này nhận được là ~ 3^2 × 1 + 1^2 × 2 + 2^2 × 3 = 23 ~.

Yêu cầu: Hãy cho biết giá trị của món quà mà mỗi lập trình viên nhận được.

Dữ liệu vào

• Dòng đầu tiên ghi 2 số nguyên dương ~ n, m ~ ~ ( 1 ≤ n, m ≤ 2 × 10^5 ) ~.
• Dòng thứ 2 ghi lần lượt các số ~ a_1, a_2, …,a_n ~.
• Dòng thứ ~ i ~ trong ~ m ~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~ l_i, r_i ~.

Kết quả

Gồm ~ m ~ số tương ứng với giá trị món quà sau khi gộp của ~ m ~ lập trình viên nhận được. Mỗi số ghi trên một dòng.

Ràng buộc

• Có 25% số test có: ~ n, m ≤ 2000, 1 ≤ a_i ≤ 10 ~.
• Có 25% số test có: ~ n, m ≤ 2 × 10^5, 1 ≤ a_i ≤ 10 ~.
• Có 25% số test có: ~ n, m ≤ 2000, 1 ≤ a_i ≤ 10^6 ~.
• Có 25% số test có: ~ n, m ≤ 2 × 10^5, 1 ≤ a_i ≤ 10^6 ~

Ví dụ:

Input 1

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

Output 1

23
6
16