T217124 [FTLOI R1]佳肴

zqw 为了庆祝自己 $\texttt{CSP-S}$ 一等，特意整了满满一桌佳肴。

他有 $n$ 个菜，整齐的排列在桌上，分别编号 $1,2\cdots n$，每个食物也有一个美味值（$w_i\in[1,n]$），每次 zqw 会选择一个区间 $[l,r]$ 里的食物来吃（所有的食物都必须吃完），于是他就产生了一个满足感。 - 当某个美味值只吃了一次时，zqw 觉得太少了。 - 当某个美味值刚好吃了两次时，zqw 就会感到很满足，他的满足感会 +1。 - 当某个美味值吃了超过两次时，zqw 就感到十分的腻，他的满足感会 -1。 注意：满足感与吃的顺序无关，只与美味值出现总数有关，因为我们假设 zqw **同时**吃掉所有食物。 现在 zqw 希望让你告诉他每次选择的食物会给他带来多少满足感。 举个栗子： $1\ \ 2\ \ 2\ \ 3\ \ 3\ \ 3\ \ 3$。 这里的 $1$ 出现了一次，不影响。 这里的 $2$ 出现了两次，满足感 $+1$。 这里的 $3$ 出现了四次，满足感 $-1$。 于是最后的满足感是 $0$。

第一行，两个整数 $n,m$，分别表示 zqw 整的佳肴的个数和他的询问数。 第二行，有 $n$ 个整数，表示第 $i$ 个菜的美味值 $w_i$。 接下来有 $m$ 行，每行两个整数 $l,r$，意思参考题目描述，这里请将 $l,r$ 与上一次询问的答案 $\text{abs}(lastans)$ 异或，如果没有上一次询问，则默认为 $lastans=0$。 **注意：** 有可能 $l'>r'$ 需要交换，还要将 $l,r$ 与 $n$ 求最小值，和 $1$ 求最大值（异或完可能大于 $n$，出题人也不知道其他强制在线的题怎么做到不爆出 $n$ 的）。

共 $m$ 行，对于 zqw 的每个询问，输出他会获得的满足感。

#### **本题采用捆绑测试**。 对于 $100\%$ 的数据，$1\leq n,m\leq3\times10^5$，$1\leq l,r\leq n$，$1\leq w_i\leq n$。 subtask1（data1~5），保证 $n,m\leq10^2$，且数据随机，$1s$。 subtask2（data6~10），保证 $n,m\leq10^4$，且数据随机，$1s$。 subtask3（data11~15），保证 $n,m\leq3\times10^5$ 且数据随机，$3s$。 subtask4（data16~20），保证 $n,m=3\times10^5$ 且数据不随机，$2s$。 本题的时间限制比 std 多 $\text{700ms}$。