Description

You are given a sequence $s$ of length $n$.

There are $q$ queries. Each query is in the form a b c d e f, and you need to compute the value of the following expression:

$$\sum_{L=a}^{b}[e\le G(F(L,c),F(L,c+1),\cdots,F(L,d))\le f]$$

Here, $F(l,r)$ denotes the number of distinct values in the subarray $[l,r]$ of sequence $s$, and $G(x_1,x_2,\cdots,x_k)$ denotes the number of distinct values among $x_1,x_2,\cdots,x_k$.

Input Format

The first line contains two integers $n,q$, representing the length of the sequence and the number of queries.

The second line contains $n$ integers, where the $i$-th integer represents $s_i$.

The next $q$ lines each contain $6$ integers $a',b',c',d',e,f$. Let the answer to the previous query be $\text{lastans}$ (in particular, if this is the first query, then $\text{lastans}=0$). Then in this query: $a=(a'+\text{lastans})\bmod n+1\\$ $b=(b'+\text{lastans})\bmod n+1\\$ $c=(c'+\text{lastans})\bmod n+1\\$ $d=(d'+\text{lastans})\bmod n+1\\$

Note that you need to reorder $a,b,c,d$ so that $a\le b\le c\le d$.

Output Format

For each query, output the answer in order.

3 1
2020 2021 2020
3 3 2 2 1 1

1

10 3
2 2 4 3 5 3 5 4 1 2
3 5 2 4 1 2
5 7 2 9 2 4
1 3 1 8 1 3

2
4
4

Hint

[Sample 1 Explanation]

In the first query, $a=1,b=1,c=3,d=3,e=1,f=1$.

It is easy to get $G(F(1,3))=1$, and $e\le G(F(1,3))\le f$, so the answer is $1$.

[Sample 2 Explanation]

Query ID	$a$	$b$	$c$	$d$	$e$	$f$
①	3	4	5	6	1	2
②	2	5	8	10	2	4
③	3	6		8	1	3

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n,q\le500$, $1\le s_i\le10^6$.
• Subtask 2 (15 pts): $n,q\le3\times10^3$.
• Subtask 3 (20 pts): $b-a\le20$.
• Subtask 4 (25 pts): $n,q\le10^5$.
• Subtask 5 (30 pts): no special constraints.

For $100\%$ of the testdata, $1\le n,q\le3\times10^5$, $0\le|s_i|\le10^9$. For all queries, $1\le a,b,c,d\le n$, $0\le e\le f\le n$.

[Hint]

1. In this problem, $[x \le y \le z]$ indicates whether $y$ is $\in[x,z]$. If it is in this interval, the value is $1$; otherwise it is $0$.

2. The input size is large, so please use a faster input method.

Translated by ChatGPT 5