Cho dãy gồm \(n\) số nguyên dương \(a_1, a_2,...a_n\). Với mỗi dãy con \(a_l, a_{l+1},...,a_r\) \((1 \le l \le r \le n)\) và số nguyên dương \(k\). Đặt \(F_k\) là số lần xuất hiện của \(k\) trong dãy con đó.

Ví dụ, cho dãy gồm \(8\) số nguyên \({1,1,2,2,1,3,1,1}\). Dãy con với \((l=2, r=7)\) có \(F_1=3\), \(F_2=2\), \(F_3=1\); với \(k \gt 3\) thì \(F_k=0\)

Yêu cầu

• Cho \(T\) dãy con có dạng \((l,r,k)\); hãy xác định giá trị \(F_k\) của mỗi dãy con?

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(T\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2...a_n\) phân tách nhau bởi dấu cách.
• Trên \(T\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(l,r,k\) thể hiện một dãy con.

Dữ liệu ra

• Gồm \(T\) dòng, dòng thứ \(i\) ghi một số nguyên là kết quả của câu hỏi thứ \(i\)

Ràng buộc

• \(1 \le n, T \le 2 \times 10^5\)
• \(1 \le a_i \le 10^9\)

Input 1

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

Output 1

2
2
2