Cho một mảng gồm n phần tử và q truy vấn. Mỗi truy vấn yêu cầu đếm số lần xuất hiện của mỗi phần tử trong đoạn [l, r].

Đầu vào

• Dòng đầu tiên chứa hai số nguyên n và q (1 ≤ n, q ≤ 105).
• Dòng thứ hai chứa n số nguyên a[i] (-106 ≤ a[i] ≤ 106).
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên l và r (1 ≤ l ≤ r ≤ n).

Đầu ra

• Với mỗi truy vấn, in ra số lần xuất hiện của mỗi phần tử trong đoạn [l, r], theo thứ tự xuất hiện lần đầu tiên trong đoạn đó.

Ví dụ

Input
7 2
3 1 2 1 3 1 4
1 6
2 5

Output
2 3 1
2 1 1