Tý cần giải bài toán sau:

Trong một cuộc khảo sát thị trường, một cửa hàng trực tuyến ghi nhận mã số của \(N\) mặt hàng đã bán ra theo thứ tự thời gian. Mỗi mặt hàng có mã số là một số nguyên dương. Người quản lý muốn thực hiện \(Q\) truy vấn: với mỗi truy vấn \((L, R, X)\), hãy cho biết mặt hàng mã \(X\) xuất hiện bao nhiêu lần trong đoạn giao dịch từ thời điểm \(L\) đến thời điểm \(R\).

Hãy lập trình giúp người quản lý cửa hàng.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) — mã các mặt hàng (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L, R, X\) (\(1 \le L \le R \le N\), \(1 \le X \le 10^9\)).

Định dạng đầu ra

• In ra \(Q\) dòng, dòng thứ \(i\) là số lần xuất hiện của \(X\) trong đoạn \([L, R]\) tương ứng.

Ví dụ

Input:

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

Output:

1
3
1

Giải thích:

• \([2,5]\): \(\{1,3,2,1\}\) — số 1 xuất hiện 1 lần.
• \([1,6]\): \(\{2,1,3,2,1,2\}\) — số 2 xuất hiện 3 lần.
• \([3,4]\): \(\{3,2\}\) — số 3 xuất hiện 1 lần.

Subtask