Cho dãy số nguyên \(n\) phần tử \(a_1, a_2, ..., a_n\), trả lời các truy vấn như sau:

• xét đoạn liên tiếp từ \(l\) đến \(r\)
• với mỗi cặp \((x, y)\) mà \(l\le x\le y\le r\) tính khoảng cách hamming của hai dãy \(\{a_x, a_{x + 1}, ..., a_y\}\) và dãy \(\{a_l, a_{l + 1}, ..., a_{l + y - x}\}\)
• tính tổng khoảng cách hamming của tất cả các cặp \((x, y)\)

Input

• Dòng đầu chứa hai số \(n, q\) (\(1\le n, q\le 2\cdot 10^5\))

• Dòng hai chứa \(n\) số \(a_i\) (\(1\le a_i\le 10^6\))

• \(q\) dòng tiếp theo mỗi dòng chứa hai số \(l, r\) mô tả các truy vấn

Output

• Ghi ra \(q\) dòng tương ứng với kết quả của các truy vấn.

Example

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

0
1
4
8