Tý có một kỹ thuật viên đang kiểm tra các cặp thiết bị điện tử trong một dây chuyền sản xuất gồm \(N\) thiết bị xếp thẳng hàng, mỗi thiết bị có một mã định danh là số nguyên dương. Kỹ thuật viên muốn thực hiện \(Q\) truy vấn: trong đoạn thiết bị từ vị trí \(L\) đến \(R\), có bao nhiêu cặp \((i,j)\) với \(L \le i < j \le R\) thỏa mãn mã định danh của hai thiết bị là bằng nhau (hay phép toán \(XOR\) của chúng bằng \(0\))?

Hãy giúp kỹ thuật viên viết chương trình xử lý các truy vấn.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• In ra \(Q\) dòng, mỗi dòng là số cặp \((i,j)\) có giá trị bằng nhau trong đoạn tương ứng.

Ví dụ

Input:

6 3
1 2 1 3 2 1
1 3
2 5
1 6

Output:

1
1
4

Giải thích:

• \([1,3]\): \(\{1,2,1\}\) có 1 cặp \((1,3)\).
• \([2,5]\): \(\{2,1,3,2\}\) có 1 cặp \((2,5)\).
• \([1,6]\): \(\{1,2,1,3,2,1\}\) có 4 cặp: \((1,3), (1,6), (3,6), (2,5)\).

Subtask