题目描述

给定一个长度为 $n$ 的序列 $s$。

$q$ 次询问，每个询问形如 a b c d e f，需要你求出下面式子的值：

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

这里 $F(l,r)$ 表示 $s$ 序列区间 $[l,r]$ 中不同的数的个数，$G(x_1,x_2,\cdots,x_k)$ 表示 $x_1,x_2,\cdots,x_k$ 中不同的数的个数。

输入格式

第一行两个整数 $n,q$，表示序列长度与命令次数。

第二行输入 $n$ 个整数，第 $i$ 个数表示 $s_i$。

下面 $q$ 行，每行输入 $6$ 个数 $a',b',c',d',e,f$。令上一次询问的答案为 $\text{lastans}$（特别的，若这是第一次询问，则 $\text{lastans}=0$），则本次询问中

$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\\$

注意，你需要将 $a,b,c,d$ 重新排序使得 $a\le b\le c\le d$。

输出格式

对于每次询问，依次输出答案。

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

提示

【样例一解释】

第一次询问中，$a=1,b=1,c=3,d=3,e=1,f=1$。

不难得到 $G(F(1,3))=1$，且 $e\le G(F(1,3))\le f$，所以答案为 $1$。

【样例二解释】 | 询问编号 | $a$ | $b$ | $c$ | $d$ | $e$ | $f$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | ① | 3 | 4 | 5 | 6 | 1 | 2 | | ② | 2 | 5 | 8 | 10 | 2 | 4 | | ③ | 3 | 6 | 6 | 8 | 1 | 3 |

【数据范围】

本题采用捆绑测试。

• Subtask1（10pts）：$n,q\le500$，$1\le s_i\le10^6$；
• Subtask2（15pts）：$n,q\le3\times10^3$；
• Subtask3（20pts）：$b-a\le20$；
• Subtask4（25pts）：$n,q\le10^5$；
• Subtask5（30pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1\le n,q\le3\times10^5$，$0\le|s_i|\le10^9$，对于所有询问，$1\le a,b,c,d\le n$，$0\le e\le f\le n$。

【提示】

1. 本题中，$[x \le y \le z]$ 表示 $y$ 是否 $\in[x,z]$。如果在该区间内，则值为 $1$；否则为 $0$。

2. 输入量较大，请采用较快的读入方式。