M. Ultimate K-Query
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers. You must process $$$q$$$ queries of the form $$$(l, r, k)$$$, where you need to count how many distinct values appear exactly $$$k$$$ times in the subarray $$$a[l..r]$$$.

The queries are online: the actual parameters of each query depend on the answer to the previous query. Specifically, if $$$\text{last}$$$ is the answer to the previous query (with $$$\text{last} = 0$$$ initially), then the actual query parameters are: $$$$$$l' = ((l \oplus \text{last}) \mod n) + 1$$$$$$ $$$$$$r' = ((r \oplus \text{last}) \mod n) + 1$$$$$$ where $$$\oplus$$$ denotes the XOR operation. If $$$l' \gt r'$$$, swap them.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 * 10^5$$$) — the size of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.

Each of the next $$$q$$$ lines contains three integers $$$l$$$, $$$r$$$, and $$$k$$$ ($$$1 \leq l, r, k \leq n$$$) — the encoded query parameters.

Output

For each query, output a single integer — the number of distinct values that appear exactly $$$k$$$ times in the subarray $$$a[l'..r']$$$.

Examples
Input
1 1
1
1 1 1
Output
1
Input
9 8
3 3 3 3 4 4 4 4 5
1 7 3
2 4 1
1 9 3
8 8 1
5 8 4
2 4 2
7 7 1
9 9 1
Output
1
1
0
1
1
1
1
1