Kỳ thi HSG Huyện Lệ Thủy đã đến gần, chỉ còn vài ngày nữa thôi! Nhưng trong những ngày tháng vừa qua, Nobita đã phải chép code của Dekisugi nhiều lần. Do đã bị bắt chép code \(3\) lần, tài khoản của Nobita và Dekisugi đã bị ban vĩnh viễn nên bây giờ không thể ôn tập trên LTOJ được nữa. Và giờ chỉ còn một cách duy nhất để được mở lại tài khoản đó chính là giải bài toán dưới đây.
Cho dãy số nguyên dương \(N\) phần tử \(a_1,a_2,...,a_n\) và \(Q\) truy vấn. Với mỗi truy vấn có dạng \(l\) \(r\) \(x\), hãy đếm số phần tử \(x\) trong đoạn \(l\) \(r\)

Tuy nhiên, Nobita không biết nên giải quyết bài toán thế nào để có thể \(AC\) nên Nobita đã cầu xin bạn giúp đỡ, hãy giúp Nobita nhé.

Dữ liệu vào

Dữ liệu nhập từ tệp văn bản TRUYVANX.INP

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\).\(( 1 \leq N,Q \leq 5.10^6)\)
• Dòng thứ hai chứa \(N\) số nguyên dương.\((a_i \leq 10^9)\)
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn cần xử lý.

Dữ liệu ra

Dữ liệu in ra tệp văn bản TRUYVANX.OUT
- \(Q\) dòng,mỗi dòng là đáp án của mỗi truy vấn

Subtasks

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

1
2
0