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 \leq a_{i} \leq 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}\) \(\left( 1 \leq l_{i} \leq r_{i} \leq n \right)\). 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},\ldots,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} \times 1 + s_{2}^{2} \times 2 + s_{3}^{2} \times 3 + \ldots + s_{10^{6}}^{2} \times 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},\ldots,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} \times 1 + 1^{2} \times 2 + 2^{2} \times 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: Từ tệp GOPQUA.INP

+ Dòng đầu tiên ghi 2 số nguyên dương \(n,\ m\ (1 \leq n,\ m \leq 2 \times 10^{5})\).

+ Dòng thứ 2 ghi lần lượt các số \(a_{1},a_{2},\ldots,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ả: ghi vào tệp GOPQUA.OUT 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.

Ví dụ:

Giới hạn:

• Có 25% số test tương ứng với 25% số điểm có: \(n,m \leq 2000,\ 1 \leq a_{i} \leq 10\).

• Có 25% số test khác tương ứng với 25% số điểm có: \(n,m \leq 2 \times 10^{5},\ 1 \leq a_{i} \leq 10\).

• Có 25% số test khác tương ứng với 25% số điểm có: \(n,\ m \leq 2000,\ 1 \leq a_{i} \leq 10^{6}\).

• Có 25% số test khác tương ứng với 25% số điểm có: \(n,\ m \leq 2 \times 10^{5},\ 1 \leq a_{i} \leq 10^{6}\).