Shizuka đã bị dính lời nguyền sẽ kết hôn với Degisuki. Để giải được lời nguyền đó Nobita phải giải quyết bài toán sau. Cho một dãy gồm \(n\) số nguyên không âm \(a_1, a_2, a_3, ..., a_n\). Có \(q\) truy vấn \(x, l, r\), cần tính trong đoạn \(l, r\) số \(x\) xuất hiện bao nhiêu lần. Các bạn hãy giúp Nobita phá bỏ lời nguyền đó nha!!!!

Input

• Dòng đầu tiên chứa 2 số \(n, q (1 \leq n, q \leq 10^5)\)
• Dòng thứ hai gồm \(a_1, a_2, a_3, ..., a_n (1 \leq a_i \leq 10^6)\)
• Gồm \(q\) dòng chứa \(x, l, r (1 \leq x \leq 10^6, 1 \leq l \leq r \leq n)\)

Output

• Ghi ra \(q\) dòng là kết quả mỗi truy vấn

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \cdot q \leq 10^8\)
• Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm

Example

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

0
1
1
2
1