Prefix MEX — Eolymp

Input

The first line contains two integers $n$ and $q$ ( $1 \leq n, q \leq 3 \cdot 1 0^{5}$ 1 \le n,q \le 3 \cdot 10^5) — the length of the array and the number of queries, respectively.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1,a_2,\ldots,a_n ( $0 \leq a_{i} \leq n$ 0 \le a_i \le n).

Each of the next $q$ lines contains five integers $L$ , $R$ , $k$ , $l$ , $r$ ( $1 \leq L \leq R \leq n$ 1 \le L \le R \le n, $1 \leq k \leq 1 0^{9}$ 1 \le k \le 10^9, $1 \leq l \leq r \leq R - L + 1$ 1 \le l \le r \le R-L+1).

Output

For each query, output one integer — the sum

d_{l} + d_{l + 1} + \dots + d_{r},

d_l+d_{l+1}+\ldots+d_r,

where

d = g (k, [a_{L}, a_{L + 1}, \dots, a_{R}]) .

d=g(k,[a_L,a_{L+1},\ldots,a_R]).

Print the answers to the queries in separate lines.

Examples

Example 1

Loading

Note

In the first query, we have

b = [a_{2}, a_{3}, a_{4}] = [2, 0, 1] .

b=[a_2,a_3,a_4]=[2,0,1].

The prefix MEX values of this array are

f (b) = [0, 1, 3] .

f(b)=[0,1,3].

Since $k = 1$ k=1, we have $d = [0, 1, 3]$ d=[0,1,3]. We need to find the sum of the elements from position $2$ to position $3$ :

d_{2} + d_{3} = 1 + 3 = 4.

d_2+d_3=1+3=4.

In the second query, we have

b = [1, 2, 0, 1, 3, 1] .

b=[1,2,0,1,3,1].

After the first application of function $f$ , we get

f (b) = [0, 0, 3, 3, 4, 4] .

f(b)=[0,0,3,3,4,4].

Apply function $f$ once more:

f (f (b)) = [1, 1, 1, 1, 1, 1] .

f(f(b))=[1,1,1,1,1,1].

Thus,

d = g (2, b) = [1, 1, 1, 1, 1, 1],

d=g(2,b)=[1,1,1,1,1,1],

so the sum of all its elements is

1 + 1 + 1 + 1 + 1 + 1 = 6.

1+1+1+1+1+1=6.

In the third query, consider the array

b = [a_{4}] = [1] .

b=[a_4]=[1].

Its only prefix has MEX equal to $0$ , so

d = f (b) = [0] .

d=f(b)=[0].

Therefore, the answer is $0$ .

Scoring

Subtask $1$ ( $10$ points): $L = R$ L = R for all queries.
Subtask $2$ ( $15$ points): $a_{i} = a_{i + 1}$ a_i = a_{i+1} for all $1 \leq i < n$ 1 \le i < n.
Subtask $3$ ( $10$ points): $k = 1 0^{9}$ k = 10^9 for all queries.
Subtask $4$ ( $25$ points): $n, q, k \leq 100$ n,q,k \le 100.
Subtask $5$ ( $30$ points): $n, q \leq 1000$ n,q \le 1000.
Subtask $6$ ( $40$ points): $l \neq = r$ l \ne r, $k \neq = 2$ k \ne 2 for all queries.
Subtask $7$ ( $40$ points): $L = 1$ L = 1, $k \neq = 2$ k \ne 2 for all queries.
Subtask $8$ ( $60$ points): $k = 2$ k = 2 for all queries.
Subtask $9$ ( $60$ points): $L = 1$ L = 1 for all queries.
Subtask $10$ ( $210$ points): No additional constraints.