Cho mảng A gồm N phần tử (đánh số từ 1). Có Q truy vấn, mỗi truy vấn cho ba số l, r, x. Hãy đếm số lần xuất hiện của giá trị x trong đoạn A[l..r].

Sử dụng rời rạc hoá kết hợp với kỹ thuật nén mỗi giá trị thành một vector chỉ số (hoặc prefix sum trên từng giá trị) để trả lời nhanh mỗi truy vấn.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên N (1 ≤ N ≤ 10^5) và Q (1 ≤ Q ≤ 10^5).
• Dòng thứ hai chứa N số nguyên A_i (-10^9 ≤ A_i ≤ 10^9).
• Q dòng tiếp theo, mỗi dòng chứa ba số nguyên l, r, x (1 ≤ l ≤ r ≤ N).

Đầu ra

Với mỗi truy vấn, in ra một số nguyên là số lần xuất hiện của x trong đoạn [l, r].

Ví dụ

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

Output:
2
2
2
3

Giải thích

• Truy vấn 1: [1,5] có A[1]=2, A[3]=2 → 2 lần.
• Truy vấn 2: [2,7] có A[5]=4, A[7]=4 → 2 lần.